最短路径

典型用途

交通网络问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？

交通网络用有向图来表示： 顶点：表示地点 弧：表示两个地点有路连通 弧上的权值：表示两地点之间的距离、交通费或中途花费的时间等。

如何能够使一个地点到另一个地点的运输时间最短或运费最省？这就是一个求两个地点间的最短路径问题。

问题抽象

在有向网中A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。

两种常见的最短路径问题

第一类：两点间的最短路径

第二类：某源点到其他所有顶点的最短路径

解决方法

1. 单源最短路径 Dijkstra(迪杰斯特拉)算法
2. 所有顶点间的最短路径 Floyd(弗洛伊德)算法

首先，在不考虑时间复杂度的情况下，同是解决图论中最短路径的寻找的问题。这个基础的问题之上还可以引申出很多其他的理论或是实际应用问题。Dijkstra进行进一步的堆优化以后时间复杂度成为O(nlogn)，比起Floyd的O(n^3)是小了非常非常多。但是Dijkstra，以及常用的还有Bellman-Ford，SPFA等，均是在求单源最短路径的问题中有着较为理想的时间复杂度(<=O(n^2))，但若是求图中任意两点间的距离，尤其是在图较为稠密时，Floyd的O(n^3)也是不输于其他的。另外Floyd有一个优势，那便是写起来简单。插点的简单思想，三重循环加一个判定，五行就写完了。而Dijkstra在堆优化后、以及SPFA，则需要约50行的代码。