登录
注册
开源
企业版
高校版
搜索
帮助中心
使用条款
关于我们
开源
企业版
高校版
私有云
Gitee AI
NEW
我知道了
查看详情
登录
注册
12月28日,「开源中国源创会年终盛典」珠海站再次回归!点击免费报名参会
代码拉取完成,页面将自动刷新
捐赠
捐赠前请先登录
取消
前往登录
扫描微信二维码支付
取消
支付完成
支付提示
将跳转至支付宝完成支付
确定
取消
Watch
不关注
关注所有动态
仅关注版本发行动态
关注但不提醒动态
1
Star
1
Fork
0
小白
/
算法模板整理
代码
Issues
1
Pull Requests
0
Wiki
统计
流水线
服务
Gitee Pages
JavaDoc
PHPDoc
质量分析
Jenkins for Gitee
腾讯云托管
腾讯云 Serverless
悬镜安全
阿里云 SAE
Codeblitz
我知道了,不再自动展开
更新失败,请稍后重试!
Issues
/
详情
移除标识
内容风险标识
本任务被
标识为内容中包含有代码安全 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 到其余各点的最短值。 ![输入图片说明](https://images.gitee.com/uploads/images/2021/0711/213859_9c495444_8927650.png "屏幕截图.png") # 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 到其余各点的最短值。 ![输入图片说明](https://images.gitee.com/uploads/images/2021/0711/213859_9c495444_8927650.png "屏幕截图.png") # 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 帐号,请先登录后再操作。
立即登录
没有帐号,去注册