最短路问题, 本條目存在以下問題, 請協助改善本條目或在討論頁針對議題發表看法, 此條目没有列出任何参考或来源, 2015年2月15日, 維基百科所有的內容都應該可供查證, 请协助補充可靠来源以改善这篇条目, 无法查证的內容可能會因為異議提出而移除, 此條目可参照英語維基百科相應條目来扩充, 2020年10月1日, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, temp. 本條目存在以下問題 請協助改善本條目或在討論頁針對議題發表看法 此條目没有列出任何参考或来源 2015年2月15日 維基百科所有的內容都應該可供查證 请协助補充可靠来源以改善这篇条目 无法查证的內容可能會因為異議提出而移除 此條目可参照英語維基百科相應條目来扩充 2020年10月1日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 最短路径问题是图论研究中的一个经典算法问题 旨在寻找图 由结点和路径组成的 中两结点之间的最短路径 算法具体的形式包括 确定起点的最短路径问题 也叫单源最短路问题 即已知起始结点 求最短路径的问题 在边权非负时适合使用Dijkstra算法 若边权为负时则适合使用Bellman ford算法或者SPFA算法 确定终点的最短路径问题 与确定起点的问题相反 该问题是已知终结结点 求最短路径的问题 在无向图中该问题与确定起点的问题完全等同 在有向图中该问题等同于把所有路径方向反转的确定起点的问题 确定起点终点的最短路径问题 即已知起点和终点 求两结点之间的最短路径 全局最短路径问题 也叫多源最短路问题 求图中所有的最短路径 适合使用Floyd Warshall算法 一个有6个节点和7条边的图 用于解决最短路径问题的算法被称做 最短路径算法 有时被简称作 路径算法 最常用的路径算法有 Dijkstra算法 A 算法 Bellman Ford算法 SPFA算法 Bellman Ford算法的改进版本 Floyd Warshall算法 Johnson最短路算法 英语 Johnson s algorithm 双向搜索目录 1 单源最短路径算法 1 1 无向图 1 2 无权图 1 3 有向无环图 1 4 无负权的有向图 2 参见单源最短路径算法 编辑无向图 编辑 权值要求 时间复杂度 作者ℝ O V 2 displaystyle O V 2 Dijkstra 1959ℝ O E V log V displaystyle O E V log V Johnson 1977 二叉堆 ℝ O E V log V displaystyle O E V log V Fredman amp Tarjan 1984 斐波那契堆 ℕ O E displaystyle O E Thorup 1999 要求常数时间复杂度的乘法 无权图 编辑 算法 时间复杂度 作者广度优先搜索 O E V displaystyle O E V Konrad Zuse 1945 Moore 1959有向无环图 编辑 使用拓扑排序算法可以在有权值的DAG中以线性时间 8 E V displaystyle theta E V 求解单源最短路径问题 无负权的有向图 编辑 假设边缘权重均为整数 算法 时间复杂度 作者O V 2EL Ford 1956Bellman Ford 算法 O VE Shimbel 1955 Bellman 1958 Moore 1959O V 2 log V Dantzig 1960Dijkstra s 算法 列表 O V 2 Leyzorek et al 1957 Dijkstra 1959 Minty see Pollack amp Wiebenson 1960 Whiting amp Hillier 1960Dijkstra s 算法 二叉堆 O E V log V Johnson 1977 Dijkstra s 算法 斐波那契堆 O E V log V Fredman amp Tarjan 1984 Fredman amp Tarjan 1987O E log log L Johnson 1981 Karlsson amp Poblete 1983Gabow s 算法 O E logE V L Gabow 1983 Gabow 1985O E V log l displaystyle O E V sqrt log l Ahuja et al 1990Thorup O E V log log V Thorup 2004参见 编辑 计算机科学主题 计算机程序设计主题 图论 离散数学 算法导论 寻路 IEEE 802 1aq 网络流 最短路徑樹 取自 https zh wikipedia org w index php title 最短路问题 amp oldid 69151213, 维基百科，wiki，书籍，书籍，图书馆，
