Dijkstra算法求图中最短路径

在此借用上一篇文章深度优先搜索（DFS）两点之间的可行路径中的例子：

简单的有向无权图

而Dijkstra主要用于解决有权图的最短路径求解，为了更好地演示Dijkstra的过程，可以为这个图的边加上权重，可以认为边的权重即为两点之间的距离：

有向有权图

显然，从1到6的路径中，权重和最短的路径有两条，一条是[1,2,4,5,6]，另一条是[1,3,6]，距离都是4。但是更大的图就不能仅凭肉眼判断了，下面将演示如何使用Dijkstra算法求出图中两点之间的距离。

graph = [
[2,3],
[4],
[4,6],
[5],
[6],
]
inf = 99999999
distance = [
    [0,1,2,inf,inf,inf],
    [inf,0,inf,1,inf,inf],
    [inf,inf,0,2,inf,2],
    [inf,inf,inf,0,1,inf],
    [inf,inf,inf,inf,0,1],
    [inf,inf,inf,inf,inf,0]
]


S = 1
D = 6

def Dijkstra(graph):
    dis = distance[S-1]
    # 最初U中只包含起点
    U = [[S,[None],0]]
    points = [i+1 for i in range(6)]
    points.remove(S)
    # V中包含除起点外的其他店
    V = [[c,[S],dis[c-1]] for c in points]
    while V:
        # 从大到小排列
        V = sorted(V,key=lambda x:x[2],reverse=True)
        # 从V中取距离S最近的点，加入U中
        item = V.pop()
        U.append(item)
        # 如果找到了终点就提前停止
        if item == D:
            break
        # 遍历V，更新各点距离
        for i,c in enumerate(V):
            # 如果某点到S的距离小于某点经由item[0]（上一个找到的点）到S的距离
            # 则更新该点坐标，并将上一个找到的点作为该点的前置点
            if dis[c[0]-1] > dis[item[0]-1] + distance[item[0]-1][c[0]-1]:
                dis[c[0]-1] = dis[item[0]-1] + distance[item[0]-1][c[0]-1]
                distance[S-1][c[0]-1] = dis[item[0]-1] + distance[item[0]-1][c[0]-1]
                # 更新前置点
                V[i][1] = [item[0]]
                # 更新距离
                V[i][2] = dis[c[0]-1]
            elif dis[c[0]-1] == dis[item[0]-1] + distance[item[0]-1][c[0]-1]:
                # 添加前置点
                V[i][1].append(item[0])
            else:
                pass
    return U

U = Dijkstra(graph)
print(U)

output:
[[1, [None], 0], [2, [1], 1], [3, [1], 2], [4, [2], 2], [5, [4], 3], [6, [3, 5], 4]]

可以看到从1到6的最短距离为4，并且路径中沿途的点都已经记录下来了。

对机器学习与算法感兴趣的朋友可以加群：

机器学习-菜鸡互啄