dijkstra

微信截图_20200525173649.png

如图所示，dijkstra算法需要的几个关键变量如下：

visited: 标识已经被访问过的节点，即该节点的所有邻接节点都已探索过了。
初始化时是空列表 [ ]，之后不断向里面添加访问过的节点
unvisit: 标识未被访问的节点，也是即将要被访问的节点，需要按链路距离逐层添加。
初始化时是只有源节点的列表 [ src ] ，之后按其到源节点的链路距离逐个添加。
链路距离表示两节点的跳数。如A到C的链路距离为2.
如图，如果规定A为源节点，则由A首先探索其邻接节点B，D，此时unvisit = [ B , D ]，（注，A已经被拿来探索了，所以已经被pop出了unvisit列表），然后下一个循环，从 unvisit中pop出B, 探索B的邻接节点，并加入到unvisit中，此时unvisit = [ D, E, C ]。

一个如图的结构体
typedef result{
int vertex;
float dis;
int preVertex;
}
则一个保存源节点到所有节点的距离和前驱节点的列表 results = [ result1, result2,...]
通过不断探索，不断更新最短路径和前驱节点，即可计算全图的最短路径。

最后附上python 代码：

def dijkstra(graph, src):
    visited = []
    unvisited = [ src ]
    shortestDis = [ INT_MAX for i in range(vertexNum)]
    shortestDis[src] = 0
    preVertex = [None for i in range(vertexNum)]
 
    while unvisited:
        vertex = unvisited.pop(0)
        for i in range(vertexNum):
            if graph[vertex][i] < INT_MAX and i not in visited:
                if i not in unvisit:
                    unvisited.append(i)
                tempDis = graph[vertex][i] + shortestDis[vertex]
                if tempDis < shortestDis[i]:
                    shortestDis[i] = tempDis
                    preVertex[i] = vertex
        visited.append(vertex)