登录
注册
开源
企业版
高校版
搜索
帮助中心
使用条款
关于我们
开源
企业版
高校版
私有云
模力方舟
登录
注册
医疗 AI 怎么落地?本周四晚 19:30,「智医灵枢」开发者直播开讲,来听听一线医院的实战分享!
代码拉取完成,页面将自动刷新
捐赠
捐赠前请先登录
取消
前往登录
扫描微信二维码支付
取消
支付完成
支付提示
将跳转至支付宝完成支付
确定
取消
Watch
不关注
关注所有动态
仅关注版本发行动态
关注但不提醒动态
1
Star
1
Fork
0
小白
/
算法模板整理
代码
Issues
1
Pull Requests
0
Wiki
统计
流水线
服务
JavaDoc
PHPDoc
质量分析
Jenkins for Gitee
腾讯云托管
腾讯云 Serverless
悬镜安全
阿里云 SAE
Codeblitz
SBOM
我知道了,不再自动展开
更新失败,请稍后重试!
移除标识
内容风险标识
本任务被
标识为内容中包含有代码安全 Bug 、隐私泄露等敏感信息,仓库外成员不可访问
算法模板分类
待办的
#I4048M
小白
拥有者
创建于
2021-07-11 21:38
# 1.最短路径相关 ## 单源最短路 - 所有边权都是正数 - 朴素的Dijkstra算法 O(n^2) 适合稠密图 - 堆优化版的Dijkstra算法 O(mlog n)(m是图中节点的个数)适合稀疏图 - 存在负权边 - Bellman-Ford O(nm) - spfa 一般O(m),最坏O(nm) 当所有边为正的时候,以上几种算法均可使用。这里给出相关的代码模板,具体的理论大家可以自行网上查阅。 贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。 ## 迪杰斯特拉算法 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家[狄克斯特拉]狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 在有向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短值。  # 2.BFS模板 # 3.最短路径模板
# 1.最短路径相关 ## 单源最短路 - 所有边权都是正数 - 朴素的Dijkstra算法 O(n^2) 适合稠密图 - 堆优化版的Dijkstra算法 O(mlog n)(m是图中节点的个数)适合稀疏图 - 存在负权边 - Bellman-Ford O(nm) - spfa 一般O(m),最坏O(nm) 当所有边为正的时候,以上几种算法均可使用。这里给出相关的代码模板,具体的理论大家可以自行网上查阅。 贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。 ## 迪杰斯特拉算法 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家[狄克斯特拉]狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 在有向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短值。  # 2.BFS模板 # 3.最短路径模板
评论 (
0
)
登录
后才可以发表评论
状态
待办的
待办的
进行中
已完成
已关闭
负责人
未设置
标签
未设置
标签管理
里程碑
未关联里程碑
未关联里程碑
Pull Requests
未关联
未关联
关联的 Pull Requests 被合并后可能会关闭此 issue
分支
未关联
未关联
master
开始日期   -   截止日期
-
置顶选项
不置顶
置顶等级:高
置顶等级:中
置顶等级:低
优先级
不指定
严重
主要
次要
不重要
参与者(1)
1
https://gitee.com/code-to-xiaobai/algorithm-template-arrangement.git
git@gitee.com:code-to-xiaobai/algorithm-template-arrangement.git
code-to-xiaobai
algorithm-template-arrangement
算法模板整理
点此查找更多帮助
搜索帮助
Git 命令在线学习
如何在 Gitee 导入 GitHub 仓库
Git 仓库基础操作
企业版和社区版功能对比
SSH 公钥设置
如何处理代码冲突
仓库体积过大,如何减小?
如何找回被删除的仓库数据
Gitee 产品配额说明
GitHub仓库快速导入Gitee及同步更新
什么是 Release(发行版)
将 PHP 项目自动发布到 packagist.org
评论
仓库举报
回到顶部
登录提示
该操作需登录 Gitee 帐号,请先登录后再操作。
立即登录
没有帐号,去注册