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 = 99999999distance = [    [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 = 1D = 6def 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 UU = 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，并且路径中沿途的点都已经记录下来了。

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

机器学习-菜鸡互啄