最短路径Dijkstra算法

Dijkstra算法可以计算加权图一个顶点到其它各个顶点的最短路径，权值不能为负数。

无向图G.png

算法描述

将一个图的所有顶点分为 S, U 两个集合. S 表示已经求出最短路径的顶点集合， U 表示剩余未确定最短路径的顶点集合。
初始时 S 中只有一个源点，从 U 中选择一个距离源点距离最近的顶点 v 移动到 S 中，以 v 为中间顶点更新源点到 U 中各个顶点的路径长度, 只计算与 v 邻接的顶点就行了,未邻接的顶点说明暂时还不能确定最短路径, 如果找到了更短的路径就更新。重复上面操作直到 U 为空算法结束， S 就保留了源点到各个顶点的最短路径。

步骤分析

初始：
S(A:0)
U(B:6, C:3, D:∞, E:∞, F:∞)
A 为源点，源点到 B 的距离为6，到 C 的距离为 3，到D、E、F的最短路径还未确定所以赋值为无穷大
第一步：
从 U 中选择距离源点路径最短的顶点，显然是 C(3)，把 C 移动到 S 中。
S(A:0, C:3)
U(B:6, D:∞, E:∞, F:∞)
以 C 为中间点，更新源点到 U 中各个顶点的距离(只计算与 C 邻接的顶点就行)
A->C->B=5 < 6, A->C->D=6 < ∞, A->C->E=7 < ∞
更新后:
U(B:5, D:6, E:7, F:∞)
第二步：
再从 U 中选择距离源点路径最短的顶点 B(5)，重复第一步的操作，这里没有需要更新的，计算后得到
S(A:0, C:3, B:5)
U(D:6, E:7, F:∞)
第三步:
从 U 中选择 D(6), A->C->D->F=9 < ∞, 操作后得到
S(A:0, C:3, B:5, D:6)
U(E:7, F:9)
第四步:
从 U 中选择 E(7), 操作后得到
S(A:0, C:3, B:5, D:6, E:7)
U(F:9)
最后一步：
把最后一个顶点 F(9) 移动到 S 中， U 变为空
S(A:0, C:3, B:5, D:6, E:7, F:9)
所以从源点 A 到各个顶点的最短路径为:
A->A 0
A->C 3
A->B 5 (A->C->B)
A->D 6 (A->C->D)
A->E 7 (A->C->E)
A->F 9 (A->C->D->F)

代码实现

python 中可以这样表示上面的无向图

g = {
    'A': {'B': 6, 'C': 3},
    'B': {'A': 6, 'C': 2, 'D': 5},
    'C': {'A': 3, 'B': 2, 'D': 3, 'E': 4},
    'D': {'B': 5, 'C': 3, 'E': 2, 'F': 3},
    'E': {'C': 4, 'D': 2, 'F': 5},
    'F': {'D': 3, 'E': 5}
}

与邻接表类似

无穷大可以这样表示

infinity = float("inf")  # 无穷大

#!/usr/bin/env python3

def find_lowest_cost_node(U):
    lowest = infinity
    lowest_node = None
    for k, v in U.items():
        if v < lowest:
            lowest = v
            lowest_node = (k, v)

    return lowest_node


def dijkstra():
    S = {
        'A': 0
    }

    U = {
        'B': 6,
        'C': 3,
        'D': infinity,
        'E': infinity,
        'F': infinity
    }

    while len(U) > 0:  # 只要 U 不空就一直循环
        # 从 U 中寻找距离源点路径最短的顶点 v
        lowest_node = find_lowest_cost_node(U)

        # 把顶点 v 从 U 中移动到 S 中
        lowest_key, lowest_cost = lowest_node
        S[lowest_key] = lowest_cost
        del U[lowest_key]

        # 寻找与找到的路径最短的顶点的所有邻接顶点
        neighbors = g[lowest_key]
        for node in neighbors:
            if node in U.keys():
                pre_cost = U[node]
                # 以新找到的顶点重新计算路径长度
                new_cost = lowest_cost + neighbors[node]
                if new_cost < pre_cost:
                    U[node] = new_cost  # 如果找到了更短的路径则更新 U 中的路径长度

    # 因为哈希表输出顺序不固定这里排一下序
    print(sorted(S.items(), key=lambda x: x[1]))
    # [('A', 0), ('C', 3), ('B', 5), ('D', 6), ('E', 7), ('F', 9)]

最短路径的长度是计算出来了，但经过的顶点没有保存下来，可以再用一个表保存各个顶点的父结点
A B 表示 A的父结点是 B
开始 A没有父结点，B 和 C 的父结点为 A
A None
B A
C A
当 C 移动到 S 中后， A->C>B=5 < A->B=6 所以 B 的父结点应该改为 C， A->C->D=6 < ∞ 所以 D 的父结点为 C， A->C->E=7 < ∞ 所以 E 的父结点为 C
A None
B C
C A
D C
E C
当 D 移动到 S 中后，A->C->D->F=9 < ∞, F的父节点为 D
A None
B C
C A
D C
E C
F D
可见当发现了更短的路径时添加或更新父结点就行了

parent = {
     'A': None,
     'B': 'A',
     'C': 'A'
}
 
if new_cost < pre_cost:
    U[node] = new_cost  # 如果找到了更短的路径则更新 U 中的路径长度
    parent[node] = lowest_key  # 更新父结点

print(sorted(parent.items()))
# [('A', None), ('B', 'C'), ('C', 'A'), ('D', 'C'), ('E', 'C'), ('F', 'D')]

打印路径就非常简单了，这里就不写了