最短路问题 最短路径问题是图论研究中的一个经典算法问题旨在寻找图由结点和路径组成的中两结点之间的最短路径算法具体的形式包括 确定起点的最短路径问题  也叫单源最短路问题即已知起始结点求最短路径的问题在边权非负时适合使用Dijkstra算法若边权为负时则适合使用Bellmanford算法或者SPFA算法 确定终点的最短路径问题  与确定起点的问题相反该问题是已知终结结点求最短路径的问题在无向图中该问题与确定起点的问题完全等同在有向图中该问题等同于把所有路径方向反转的确定起点的问题 确定起点终点的最短路径问题  即已知起点和终点求两结点之间的最短路径 全局最短路径问题  也叫多源最短路问题求图中所有的最短路径适合使用FloydWarshall算法 用于解决最短路径问题的算法被称做最短路径算法有时被简称作路径算法最常用的路径算法有 Dijkstra算法 A算法 BellmanFord算法 SPFA算法BellmanFord算法的改进版本 FloydWarshall算法 Johnson最短路算法英语Johnsons algorithm 双向搜索