最短路问题

图论中求某点到某点最短的路径长度。

图中点1到点4的最短路径长度应为3.

分类

最短路问题分为两类：单源最短路和多源最短路。前者只需要求一个固定的起点到各个顶点的最短路径，后者则要求得出任意两个顶点之间的最短路径。

单源最短路

Dijkstra算法

Dij基于一种贪心的思想，我们假定有一张没有负边的图。首先，起点到起点的距离为0，这是没有疑问的。现在我们对起点和它能直接到达的所有点进行松弛。

因为没有负边，这时我们可以肯定，离起点最近的那个顶点的dist一定已经是最终结果。为什么？因为没有负边，所以不可能经由其他点，使起点到该点的距离变得更短。
那现在我们来考察2号点：

我们对2号点和它能到达的点进行松弛。这时dist保存的是起点直接到达或经由2号点到达每个点的最短距离。我们这时候取出未访问过的dist最小的点（即4号点），这个点的dist也不可能变得更短了（因为其他路径都至少要从起点直接到达、或者经由2号点到达另一个点，再从这另一个点到达4号点）。

继续这个流程，松弛4号点能到达的点：

然后分别考察3、5号点，直到所有点都被访问过即可。
总结一下，\(Dijkstra\)算法的流程就是，不断取出离顶点最近而没有被访问过的点，松弛它和它能到达的所有点。
如何取出离顶点最近的点？如果暴力寻找，那就是朴素的\(Dijkstra\)算法，时间复杂度是\(O(n^2)\) ，但我们可以采取堆优化。具体而言，我们可以用一个优先队列来维护所有节点。这样可以实现在 \(O(mlogm)\) 的时间内跑完最短路。