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)
最短路问题难点在于：建图
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）