快捷導(dǎo)航

Dijkstra算法詳細介紹及Python實現(xiàn)方法

更新時間：2026年03月20日 09:23:54 作者：不去幼兒園

迪杰斯特拉（Dijkstra）算法是一種用于尋找有向圖中單源最短路徑的經(jīng)典算法,在這個算法中,我們從一個源節(jié)點開始,逐步擴展最短路徑到其他節(jié)點,直到到達所有節(jié)點或者目標(biāo)節(jié)點,這篇文章主要介紹了Dijkstra算法詳細介紹及Python實現(xiàn)的相關(guān)資料,需要的朋友可以參考下

1. Dijkstra算法介紹

Dijkstra算法，全稱迪杰斯特拉算法，是由荷蘭計算機科學(xué)家艾茲赫爾·戴克斯特拉（Edsger W. Dijkstra）在1956年提出的，是一種用于解決圖中的最短路徑問題的算法。這種算法適用于帶權(quán)重的圖，其中每條邊有一個非負的權(quán)重值。

這篇論文發(fā)表于1959年的《Numerische Mathematik》期刊第1期，第269-271頁，《A Note on Two Problems in Connexion with Graphs》。在這篇論文中，他不僅描述了這個算法，還提供了第一次正式的最短路徑問題算法理論證明。這篇論文的題目雖然翻譯成中文是《關(guān)于與圖相關(guān)的兩個問題的說明》，但它在算法史上有著非常重要的地位，因為其中描述的Dijkstra算法成為了解決圖中最短路徑問題的基石。

2.文獻閱讀

《A Note on Two Problems in Connexion with Graphs》的核心內(nèi)容主要針對兩個問題：

問題1：構(gòu)造n個節(jié)點間總長度最小的樹（最小生成樹）

基本思路：將邊分為3個集合（確定屬于生成樹的邊的集合I、待選邊集合II、剩余邊集合III），將節(jié)點分為2個集合（已連接集合A、剩余節(jié)點集合B）。初始時，任選一節(jié)點作為集合A的唯一成員，所有以此節(jié)點為終點的邊放入集合II，集合I為空。
構(gòu)造步驟：
- 步驟1：從集合II中選出最短的邊，將其移出集合II并加入集合I，同時將對應(yīng)的節(jié)點從集合B轉(zhuǎn)移到集合A。
- 步驟2：考慮剛轉(zhuǎn)移到集合A的節(jié)點與集合B中節(jié)點相連的邊，若邊長比集合II中對應(yīng)邊長則被舍棄，若更短則替換集合II中的對應(yīng)邊并舍棄后者。然后返回步驟1重復(fù)此過程，直到集合II和III均為空，此時集合I中的邊即構(gòu)成所需的最小生成樹。
優(yōu)勢：相較于J.B. KRUSKAL、H. LOBERMAN和A. WEINBERGER的方法，該方法無需預(yù)先所有對邊按長度排序，且只需同時存儲最多n條邊的數(shù)據(jù)（集合I和II中的邊以及步驟2中考慮的邊），而其他方法即使邊的長度是節(jié)點坐標(biāo)的可計算函數(shù)，也需要同時存儲所有邊的數(shù)據(jù)。

問題2：尋找給定兩點P和Q間總長度最小的路徑

基本思路：利用若R是P到Q的最小路徑上的節(jié)點，則知道P到Q的最小路徑也就知道P到R的最小路徑這一事實。在解決方案中，按路徑長度遞增的順序構(gòu)造P到其他節(jié)點的最小路徑，直到到達Q。
具體步驟：
- 初始狀態(tài)：所有節(jié)點在集合C，所有邊在集合III。將節(jié)點P轉(zhuǎn)移到集合A，然后反復(fù)執(zhí)行以下步驟。
- 步驟1：考慮連接剛轉(zhuǎn)移到集合A的節(jié)點與集合B或C中的節(jié)點R的所有邊r。若R屬于集合B，判斷使用邊r是否能獲得比已知路徑更短的P到R的路徑，若不能則邊r被舍棄，若能則替換集合II中的對應(yīng)邊并舍棄后者；若R屬于集合C，則將R加入集合B并將邊r加入集合II。
- 步驟2：集合B中的每個節(jié)點通過集合I中的一條邊和集合II中的一條邊與節(jié)點P相連，每個節(jié)點B都有一個到P的距離。將集合B中到P距離最小的節(jié)點轉(zhuǎn)移到集合A，對應(yīng)的邊從集合II轉(zhuǎn)移到集合I。然后返回步驟1重復(fù)此過程，直到節(jié)點Q被轉(zhuǎn)移到集合A，此時即找到解決方案。
優(yōu)勢：與L. R. FORD的方法相比，無論邊的數(shù)量如何，該方法無需同時存儲所有邊的數(shù)據(jù)，只需存儲集合I和II中的邊，且這個數(shù)量總是小于n，同時所需的工作量也明顯更少。

總結(jié)

該論文主要介紹了兩種解決圖論問題的方法，分別針對構(gòu)造最小生成樹和尋找兩點間最短路徑。這兩種方法在數(shù)據(jù)存儲和計算工作量方面相較于其他方法具有優(yōu)勢，能夠更高效地解決相應(yīng)的問題。

《A Note on Two Problems in Connexion with Graphs》中沒有直接提及“Dijkstra算法”這個名稱。但其中提出的解決最短路徑問題的方法后來被廣泛稱為Dijkstra算法。文件中針對最短路徑問題所描述的解決方法，其核心思路與Dijkstra算法完全一致，即通過維護節(jié)點集合和邊集合的特定方式，逐步確定從起點到其他節(jié)點的最短路徑。

2.Dijkstra算法原理

想象一下，你在一座迷宮里，你想要從起點A到達終點B并找到最短的路徑，那么你可以使用Dijkstra算法。這個算法會幫助你計算出從起點到所有其他點的最短距離，并且最終告訴你到達終點B的最短路徑是什么。

核心思想：

初始化：從一個頂點開始（我們稱之為源點），將源點到自身的距離設(shè)為0，而到其他頂點的距離設(shè)為無窮大。
選擇最近頂點：在所有未被訪問過的頂點中，選擇距離源點最近的一個頂點（稱之為當(dāng)前頂點）。
更新距離：檢查通過當(dāng)前頂點可以到達的所有其他未被訪問過的頂點，如果通過當(dāng)前頂點到達這些頂點的距離比之前已知的更短，就更新這些頂點的距離。
標(biāo)記已訪問：將當(dāng)前頂點標(biāo)記為已訪問，并從待訪問頂點集合中移除。
重復(fù)以上步驟：重復(fù)步驟2到4，直到所有的頂點都被訪問過或者目標(biāo)頂點被訪問。

示例：

假設(shè)我們有如下的圖中的四個節(jié)點和它們之間的邊及其權(quán)重：

  A---(2)---B
  |         |
(3)        (1)
  |         |
  ----------------C

我們要計算從A到C的最短路徑。

初始化：
- A = 0, B = ∞, C = ∞
選擇最近的未訪問頂點B（因為它離A最近，距離為2）。
更新C的距離（因為B到C的距離是1，所以A到C的新距離是A到B的距離加上B到C的距離，即2+1=3）：
- A = 0, B = 2, C = 3
現(xiàn)在，B和C都是最近未訪問過的頂點，我們選擇B作為下一個當(dāng)前頂點（因為它先被檢查到）。
更新頂點后，沒有更短的路徑可以到達C了，我們將B標(biāo)記為已訪問。
現(xiàn)在C是唯一的未訪問頂點，我們選擇它作為當(dāng)前頂點。
最終結(jié)果是A到C的最短路徑是3。

推理公式：

Dijkstra算法沒有一個單一的公式，但是可以用偽代碼來說明它的邏輯：

function Dijkstra(Graph, source):
    dist[source] ← 0; // 初始化距離表
    for each vertex v in Graph: 
        if v ≠ source
            dist[v] ← ∞; 
            prev[v] ← undefined; // 前驅(qū)節(jié)點，用于記錄最短路徑
            Q ← all vertices in Graph; // 所有頂點的集合
    while Q is not empty:
        u ← vertex in Q with min dist[u];
        remove u from Q;
        for each neighbor v of u: // 遍歷u的所有鄰居v
            alt ← dist[u] + length(u, v);
            if alt < dist[v]:
                dist[v] ← alt;
                prev[v] ← u;
    return dist[];

這段偽代碼描述了Dijkstra算法的基本流程，其中dist[]存儲從源點到各個點的距離，prev[]用來存儲最短路徑樹，以便最后能回溯出最短路徑。

[Python] Dijkstra算法實現(xiàn)

下面給出一個簡單的Python實現(xiàn)Dijkstra算法的程序，以及一個示例圖和運行結(jié)果。這個程序會計算從源點到圖中所有其他節(jié)點的最短路徑，并輸出最短距離和路徑。

"""《Dijkstra算法程序》
    時間：2025.03.06
    作者：不去幼兒園
"""
import heapq

def dijkstra(graph, start):
    -distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    -previous_nodes = {vertex: None for vertex in graph}
    -unvisited_queue = [(0, start)]

    while unvisited_queue:
        current_distance, current_vertex = heapq.heappop(unvisited_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_vertex
                heapq.heappush(unvisited_queue, (distance, neighbor))

    return distances, previous_nodes


# Example graph represented as an adjacency list
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 4},
    'C': {'A': 3, 'B': 1, 'D': 5},
    'D': {'B': 4, 'C': 5}
}

start_vertex = 'A'
distances, previous_nodes = dijkstra(graph, start_vertex)

# Function to print the shortest path from start_vertex to end_vertex
def print_shortest_path(previous_nodes, start_vertex, end_vertex):
    path = []
    current_vertex = end_vertex
    while current_vertex is not None and current_vertex != start_vertex:
        path.insert(0, current_vertex)
        current_vertex = previous_nodes[current_vertex]
    if current_vertex is None:
        return "Path does not exist"
    else:
        path.insert(0, start_vertex)
        return path

# Output the results
print("Vertex\tDistance\tPath")
for vertex in graph:
    if vertex != start_vertex:
        dist = distances[vertex]
        path = print_shortest_path(previous_nodes, start_vertex, vertex)
        print(f"{vertex}\t{dist}\t\t{path}")

[Results] 運行結(jié)果

上述代碼中的例子圖，它展示了10個節(jié)點之間的連接關(guān)系和權(quán)重。圖形由頂點（A到J）和它們之間的邊與權(quán)重組成：

    A
   /|\
  B C D
 / | \
E  F  |
 \ | /
  G H
   \ /
    I
    |
    J

每個節(jié)點與其直接相連的節(jié)點都有特定的權(quán)重。下面是這些連接關(guān)系和對應(yīng)的權(quán)重：

A 到 B: 2
A 到 C: 3
A 到 D: 1
B 到 C: 1
B 到 D: 4
B 到 E: 5
C 到 D: 1
C 到 E: 6
D 到 E: 2
E 到 F: 7
E 到 G: 9
F 到 G: 8
F 到 H: 5
G 到 H: 3
G 到 I: 6
H 到 I: 7
I 到 J: 2

Vertex    Distance    Path
B         2          ->A->B
C         3          ->A->C
D         1          ->A->D
E         3          ->A->D->E
F         6          ->A->D->E->F
G         10         ->A->D->E->G
H         8          ->A->D->E->F->H
I         11         ->A->D->E->F->H->I
J         13         ->A->D->E->F->H->I->J

3. Dijkstra算法的應(yīng)用場景

路徑規(guī)劃：Dijkstra算法常常被用于道路網(wǎng)絡(luò)中的最短路徑查找，它可以幫助導(dǎo)航系統(tǒng)提供從起點到目的地的最佳路線。
網(wǎng)絡(luò)路由選擇：在互聯(lián)網(wǎng)中，路由器可以使用Dijkstra算法來選擇數(shù)據(jù)傳輸?shù)淖罴崖窂健?/p>
社交網(wǎng)絡(luò)分析：分析人與人之間、組織之間的最短聯(lián)系路徑。
運輸和物流領(lǐng)域：尋找貨物從一個地點到另一個地點成本最低的運輸路徑。
電路設(shè)計：在集成電路布局中，Dijkstra算法可以用于尋找最小延遲路徑。
游戲設(shè)計：游戲中的NPC（非玩家角色）導(dǎo)航和尋路系統(tǒng)可能使用Dijkstra算法確定行動路徑。
電信網(wǎng)絡(luò)：在電話網(wǎng)絡(luò)和其他電信網(wǎng)絡(luò)中定位呼叫的最佳路徑。

4.Dijkstra算法優(yōu)缺點

Dijkstra算法的優(yōu)點：

準(zhǔn)確性：Dijkstra算法總是能找到單源最短路徑的精確解，特別是當(dāng)所有邊的權(quán)重都是非負數(shù)時。
靈活性：在算法的執(zhí)行過程中如果找到從源點到目標(biāo)點的最短路徑，算法會立即停止處理該目標(biāo)點，這意味著你可以在任何時候中斷算法來查詢最短路徑。
適用于稠密圖：對于邊的數(shù)量接近于頂點數(shù)量平方的稠密圖，Dijkstra算法表現(xiàn)良好。
簡單性：算法的邏輯相對簡單，容易理解和實現(xiàn)。
可以優(yōu)先處理：通過優(yōu)先隊列的使用，Dijkstra算法可以快速訪問當(dāng)前最短路徑的節(jié)點。

Dijkstra算法的缺點：

效率問題：使用標(biāo)準(zhǔn)數(shù)組存儲距離信息時，時間復(fù)雜度為，其中V是頂點的數(shù)量。雖然通過使用斐波那契堆等優(yōu)化措施可以將時間復(fù)雜度降低到，但在最壞的情況下它仍然是效率較低的算法之一。
不適合負權(quán)重邊：Dijkstra算法不能用于包含負權(quán)邊的圖中，否則可能無法找到正確的最短路徑。
內(nèi)存消耗較大：需要存儲所有頂點的距離信息和已訪問狀態(tài)，內(nèi)存使用隨著頂點數(shù)增加而增長。
對大規(guī)模圖不友好：當(dāng)圖變得非常大時，算法將消耗較長的時間計算最短路徑。