最短路径算法

图论中求解最短路径的算法主要有两种,Dijkstra算法及Floyd算法,其中Dijkstra算法用于求解单源最短路径问题,而Floyd算法则用于解决多源最短路径问题。本文对这两种算法做一总结。

Dijkstra算法

Dijkstra算法是最经典的最短路径算法,这是一种典型的贪心算法,不过可以证明,这种贪心策略得到的就是全局最优解。Dijkstra算法的详细描述可以参考数据结构的基础书籍,以下文章也可供参考:

戴克斯特拉算法
算法 7:Dijkstra 最短路算法

Dijkstra算法的主要思想可以简要总结为:

  1. 将所有顶点分为两类,即KnownUnknown两个集合,初始时所有顶点均位于Unknown集合中,算法的目标就是将Unknown集合中的所有顶点移至Known集合中;
  2. 每一个顶点均有一个表示当前状态的属性表,其中一定要有一个变量记录此时距离源点的最短路径长度(不妨将其记为dr),除此之外根据需要还可以有一些附加信息,如最短路径来源顶点、经过的顶点数、所属的集合(Known还是Unknown)等;
  3. 初始时,源点的dr为0,其余所有顶点的dr均为无穷大,这里的无穷大只是数学上的说法,实际编程中会用一个合适的值替代;
  4. Unknown集合中选出dr最小的一个顶点,将其移至Known集合中,并更新Unknown集合中剩余顶点的dr
  5. 重复第4步,直至Unknown为空。

算法的核心就是上述步骤中的第4步,这里所谓的更新是指:遍历与选出的顶点邻接的所有顶点,若其位于Unknown集合中,比较当前dr与经由选出顶点至其的距离,若新的距离小于dr,则使用新的距离替代dr。需要注意的是,这里只更新比较位于Unknown集合中的邻接顶点,不需要去更新Known集合中的顶点,否则这就不是贪心法了。

用一张图可以很好的说明以上步骤:

下面给出Dijkstra算法的核心伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Dijkstra() {
while(!Unknown.empty()) {
V = Unknown.FindMinDr();
Unknown.remove(V);
Known.add(V);

foreach(W adjacent to V) {
if (Known.contain(W))
continue;
if (V.dr + D[v][w] < W.dr) {
W.dr = V.dr + D[v][w];
}
}
}
}

Dijkstra算法的结果一般使用一个一维表(即数组)来记录,每一项即是一个顶点对应的当前状态属性表。算法的复杂度取决于具体实现方式,一个较好的选择是使用斐波那契堆来实现,不过粗略的看,其复杂度大概是O(n^2)级别的。

Floyd算法

Floyd算法的实质是一种动态规划算法,最初不允许经由任何中间点,之后逐步添加允许的中间点,可以证明,最终允许的中间点为全部顶点时,算法得出的就是最优解。算法详细描述可见:

算法 6:只有五行的 Floyd 最短路算法

Floyd算法的核心伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// N : 顶点数
// D[N][N] : 两点间最短距离记录

void Floyd() {
for (k = 0; k < N; k++) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (D[i][j] > D[i][k] + D[k][j]) {
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
}

最外层的for循环逐渐添加允许途径的中间点,内层的两个循环遍历所有点之间的距离。Floyd算法的结果一般使用一个二维表(即二维数组)来记录,即上述代码中的D[N][N],初始值即为当前图的邻接矩阵(Adjacency Matrix)表示。算法的复杂度是O(n^3)的。