手把手教你用Python實現Dijkstra算法(偽代碼+Python實現)

最短路問題Shortest Path Problem

之前的文章中我們已經用迪傑斯特拉算法求解過Solomon算例了，今天是用該算法求解有5個點連通圖的最短路徑。大家可以看完這篇再回顧一下之前的文章。（

）

如圖所示的連通圖，以s為起點，t為終點，求一條s到t的最短路徑。

Dijkstra算法

Dijkstra算法是一種動態規劃思想的算法：

把所有的點都標記為臨時標號，每個點有兩個屬性：起點到這個點的最短距離和這個點的前序節點；將起始點的最短距離初始化為0，將其餘點的最短距離初始化為無窮大；從起始點開始，探索其子節點，更新子節點的最短距離和前序節點，當所有子節點都探索完成，則修改當前節點的標號為永久標號；選擇剩餘臨時標號的點中，最短距離最小的，作為下一個要遍歷的點，重複上述過程，直到所有節點的標號都變成永久標號為止。Dijkstra算法解決最短路問題（SPP）偽代碼
Dijkstra算法解決最短路問題（SPP）Python實現5點連通圖的最短路徑

輸入模塊

import pandas as pd 
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import copy
import re
import math
代碼語言表示文首5點連通圖
Nodes = ['s', 'a', 'b', 'c', 't']

Arecs = {('s', 'a'):5, ('s', 'b'):8, ('a', 'c'):2, ('b','a'):10, ('c','b'):3, ('b','t'):4, ('c','t'):3}
給圖中的點和弧添加屬性
Graph = nx.DiGraph()
for node in Nodes:
    Graph.add_node(node, min_dis = 0, previous_node = None)
for key in Arecs.keys():
    Graph.add_edge(key[0],key[1],length = Arecs[key])
定義用Dijkstra算法求解最短路的函數
def Dijkstra(Graph , org ,des):
 # 定義T
    T = list(Graph.nodes())
 
 # 給各點臨時標號
    for node in T:
        if (node == org) :
            Graph.nodes[node]['min_dis'] = 0
        else:
            Graph.nodes[node]['min_dis'] = np.inf
    current_node = org

    while (len(T) > 0):
        min_dis = np.inf
        
        # 更新永久標號的點
        for node in T:
            if (Graph.nodes[node]['min_dis'] < min_dis):
                current_node = node
                min_dis=Graph.nodes[node]['min_dis']
        if (current_node != None):
            T.remove(current_node)
        
        # 更新永久標號點相鄰點的臨時標號
        for child in Graph.successors(current_node):
            arc = (current_node, child)
            dis_t = Graph.nodes[current_node]['min_dis'] + Graph.edges[arc]['length']
            if (dis_t < Graph.nodes[child]['min_dis']):
                Graph.nodes[child]['min_dis'] = dis_t
                Graph.nodes[child]['previous_node'] = current_node
                
    # 確定最短路徑和最短距離
    min_dis = Graph.nodes[des]['min_dis']
    current_node = des
    shortest_path = [current_node]
    while (current_node != org):
        current_node=Graph.nodes[current_node]['previous_node']
        shortest_path.insert(0, current_node)
    return Graph, shortest_path, min_dis
調用函數求解文首的最短路徑問題
org = 's'
des = 't'
Graph, shortest_path, min_dis = Dijkstra(Graph, org, des)
結果輸出如下：(['s', 'a', 'c', 't'], 10)