微信截圖_20200525173649.png
如圖所示鞭呕，dijkstra算法需要的幾個關(guān)鍵變量如下：
visited: 標識已經(jīng)被訪問過的節(jié)點宛官，即該節(jié)點的所有鄰接節(jié)點都已探索過了。
初始化時是空列表 [ ]腋么，之后不斷向里面添加訪問過的節(jié)點
unvisit: 標識未被訪問的節(jié)點亥揖，也是即將要被訪問的節(jié)點圣勒，需要按鏈路距離逐層添加摧扇。
初始化時是只有源節(jié)點的列表 [ src ] ，之后按其到源節(jié)點的鏈路距離逐個添加扛稽。
鏈路距離表示兩節(jié)點的跳數(shù)。如A到C的鏈路距離為2.
如圖用含，如果規(guī)定A為源節(jié)點帮匾，則由A首先探索其鄰接節(jié)點B，D瘟斜，此時unvisit = [ B , D ]，（注明未，A已經(jīng)被拿來探索了壹蔓，所以已經(jīng)被pop出了unvisit列表），然后下一個循環(huán)佣蓉，從 unvisit中pop出B, 探索B的鄰接節(jié)點，并加入到unvisit中疚膊，此時unvisit = [ D, E, C ]虾标。
一個如圖的結(jié)構(gòu)體
typedef result{
int vertex;
float dis;
int preVertex;
}
則一個保存源節(jié)點到所有節(jié)點的距離和前驅(qū)節(jié)點的列表 results = [ result1, result2,...]
通過不斷探索，不斷更新最短路徑和前驅(qū)節(jié)點璧函，即可計算全圖的最短路徑。
最后附上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)
