开发者社区

文档建议反馈控制台

腾讯云架构师技术同盟

文章/答案/技术大牛

发布

社区首页 >专栏 >ACM算法竞赛——最短路知识结构总结

ACM算法竞赛——最短路知识结构总结

原创

作者头像

战士小小白

发布于 2022-05-16 10:09:15

发布于 2022-05-16 10:09:15

5280

举报

文章被收录于专栏：ACM算法竞赛——模板ACM算法竞赛——模板

n代表点数 m代表边数

最短路

1.单源最短路

····1.1所有边权都是正数

············1.1.1朴素dijkstra算法 O(n^2) 适合稠密图

············1.1.2堆优化版dijkstra算法O(mlogn) 适合稀疏图

····1.2存在负边权

············1.2.1 Bellman-Ford O(mn) (经过的边数小于等于k)

············1.2.2 SPFA 一般：O(m) 线性最坏:O（nm）

2.多源汇最短路

····2.1 Floyd算法 O(n^3)

最短路问题难点在于：建图

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

评论

登录后参与评论

0 条评论

热度

最新