通過上一章最短路徑(Bellman-Ford算法)的內(nèi)容可知多矮，Bellman-Ford 算法是通過重復(fù)對(duì)邊集執(zhí)行松弛函數(shù)褂萧，來逐漸獲得從起點(diǎn)到各個(gè)頂點(diǎn)的最短路徑嗽桩。并且對(duì)邊的松弛順序是隨意進(jìn)行的嗅骄，所以才有最好情況和最壞情況之分床绪。一般情況下則是通過不斷的對(duì)邊集進(jìn)行重復(fù)松弛机杜，來“堆”出從起點(diǎn)到其他頂點(diǎn)的最短路徑帜讲，這種“盲目”的松弛存在極多的無效操作和時(shí)間浪費(fèi)。

Dijkstra 算法使用貪心策略計(jì)算從起點(diǎn)到指定頂點(diǎn)的最短路徑椒拗，通過不斷選擇距離起點(diǎn)最近的頂點(diǎn)似将，來逐漸擴(kuò)大最短路徑權(quán)值获黔，直到覆蓋圖中所有頂點(diǎn)。

Dijkstra 算法前提為圖中邊的權(quán)值非負(fù)在验，若將最短路徑中經(jīng)過的頂點(diǎn)個(gè)數(shù)稱為最短路徑長(zhǎng)度玷氏，則最短路徑長(zhǎng)度與最短路徑權(quán)值呈正相關(guān)。而在 Bellman-Ford 算法中腋舌，因?yàn)檫叺臋?quán)值可能為負(fù)盏触，所以最短路徑長(zhǎng)度較大的頂點(diǎn)，其最短路徑權(quán)值不一定更大块饺。所以與 Bellman-Ford 算法相似赞辩，Dijkstra 算法的計(jì)算最短路徑過程，也是呈現(xiàn)一種波紋擴(kuò)散的方式授艰，不同之處在于辨嗽，Bellman-Ford 算法擴(kuò)散過程中，逐漸增大的半徑為最短路徑長(zhǎng)度淮腾，而 Dijkstra 算法的擴(kuò)大半徑為最短路徑權(quán)值糟需。

Dijkstra 算法過程中也存在對(duì)邊的松弛行為，不過該松弛過程并非“盲目”的對(duì)所有邊進(jìn)行松弛来破，而是對(duì)于已確認(rèn)頂點(diǎn)為出度篮灼，未確認(rèn)頂點(diǎn)為入度的邊進(jìn)行松弛。因?yàn)?Dijkstra 算法過程中每個(gè)頂點(diǎn)被確認(rèn)一次徘禁，所以整個(gè)算法過程只需要對(duì)邊集執(zhí)行一次松弛诅诱，即邊的松弛復(fù)雜度為 。

算法過程

1. 從未確認(rèn)頂點(diǎn)中選擇距離起點(diǎn)最近的頂點(diǎn)送朱，并標(biāo)記為已確認(rèn)頂點(diǎn)
2. 根據(jù)步驟 1 中的已確認(rèn)頂點(diǎn)娘荡，更新其相鄰未確認(rèn)頂點(diǎn)的距離
3. 重復(fù)步驟 1,2，直到不存在未確認(rèn)頂點(diǎn)

演示示例

graph

以圖 graph 為例驶沼，邊的權(quán)值如圖中所示炮沐，初始化各頂點(diǎn)距離起點(diǎn)權(quán)值為 None，不妨隨機(jī)選擇一個(gè)頂點(diǎn)作為起點(diǎn)回怜，初始化起點(diǎn)的權(quán)值為 0

選擇距離起點(diǎn)最近的頂點(diǎn)為已確認(rèn)頂點(diǎn)大年，并更新該頂點(diǎn)的相鄰未確認(rèn)頂點(diǎn)距離

step 1：

第一次選擇最近的頂點(diǎn)為起點(diǎn)自身，并更新相鄰未確認(rèn)頂點(diǎn)的距離

step 2：

step 3：

step 4：

step 5：

step 6：

step 7：

step 8：

step 9：

算法示例

1. Dijkstra 算法示例

def dijkstra(graph, start):
    vertices, verticesIndex = [{'index': i, 'weight': None} for i in range(graph.number)], [i for i in range(graph.number)]
    vertices[start - 1]['weight'] = 0
    heapSort(vertices, verticesIndex)
    while len(vertices) > 0:
        swapVertices(vertices, verticesIndex, 0, -1)
        vertex = vertices.pop()
        transformToHeap(vertices, verticesIndex, 0, len(vertices))
        updateDistance(graph, vertices, verticesIndex, vertex)

這里使用 vertices 列表存儲(chǔ)每個(gè)頂點(diǎn)元素玉雾，每個(gè)元素包括兩個(gè)屬性翔试，index 為頂點(diǎn)下標(biāo)，weight 為頂點(diǎn)距離起點(diǎn)的大小复旬。算法中使用 verticesIndex 列表存儲(chǔ)每個(gè)頂點(diǎn)元素在 vertices 列表中的下標(biāo)位置垦缅。使用 heapSort 堆排序?qū)γ總€(gè)頂點(diǎn)到起點(diǎn)的距離進(jìn)行排序，即對(duì) vertices 列表進(jìn)行排序驹碍。使用 swapVertices 函數(shù)將 vertices 列表首尾元素交換壁涎，將最小元素放置在列表尾部并執(zhí)行出棧操作凡恍，使用 transformToHeap 函數(shù)調(diào)整 vertices 列表為小頂堆，然后調(diào)用 updateDistance 函數(shù)完成對(duì)相鄰頂點(diǎn)的距離更新怔球。

2. 交換列表首尾元素

def swapVertices(vertices, verticesIndex, origin, target):
    vertices[origin], vertices[target] = vertices[target], vertices[origin]
    verticesIndex[vertices[origin]['index']], verticesIndex[vertices[target]['index']] = origin, target

當(dāng) vertices 列表調(diào)整為小頂堆之后嚼酝，將列表首、尾元素交換庞溜，則列表尾元素即為距離起點(diǎn)最近的頂點(diǎn)元素革半。

3. 將列表尾部頂點(diǎn)元素出棧后碑定，更新該頂點(diǎn)的相鄰未確認(rèn)頂點(diǎn)距離起點(diǎn)的權(quán)值

def updateDistance(graph, vertices, verticesIndex, agent):
    node = graph.list[agent['index']]
    while node:
        if verticesIndex[node.index - 1] == -1:  # whether the node in sub graph
            node = node.next
            continue
        vertex = vertices[verticesIndex[node.index - 1]]
        if not vertex['weight'] or vertex['weight'] > agent['weight'] + node.weight:
            vertex['weight'] = agent['weight'] + node.weight
            pos = verticesIndex[vertex['index']]
            while pos > 0 and (not vertices[(pos - 1) // 2]['weight'] or vertices[pos]['weight'] < vertices[(pos - 1) // 2]['weight']):
                swapVertices(vertices, verticesIndex, pos, (pos - 1) // 2)
                pos = (pos - 1) // 2
        node = node.next

對(duì)每一個(gè)相鄰頂點(diǎn)流码，若屬于未確認(rèn)頂點(diǎn)，則判斷是否更新到起點(diǎn)的距離延刘。更新距離后的 while 循環(huán)操作漫试，目的為調(diào)整堆結(jié)構(gòu)為小頂堆。

Dijkstra 算法及算法中調(diào)用的函數(shù)都與 prim 算法較大相像碘赖，可以參考最小生成樹中 prim 算法的部分作輔助理解驾荣。

性能分析

dijkstra 算法中構(gòu)造頂點(diǎn)列表的時(shí)間復(fù)雜度為 。使用堆排序?qū)旤c(diǎn)列表進(jìn)行排序普泡，時(shí)間復(fù)雜度為 播掷。dijkstra 算法中 while 循環(huán)取權(quán)值最小頂點(diǎn)元素，并調(diào)整元素取出后列表的堆結(jié)構(gòu)撼班，所以調(diào)整復(fù)雜度為 歧匈；同時(shí)，循環(huán)結(jié)構(gòu)內(nèi)執(zhí)行 updateDistance 函數(shù)砰嘁，更新每個(gè)取出頂點(diǎn)的相鄰頂點(diǎn)權(quán)值件炉，所以更新頂點(diǎn)數(shù)為 ，因?yàn)槊總€(gè)頂點(diǎn)更新距離后矮湘，需要調(diào)整堆結(jié)構(gòu)為小頂堆斟冕，所以更新復(fù)雜度為 。所以prim 算法的總時(shí)間復(fù)雜度為 缅阳。

代碼及測(cè)試 github 鏈接：最短路徑(Dijkstra算法)