DSA 迪傑斯特拉演算法
迪傑斯特拉的單源最短路徑演算法由荷蘭計算機科學家 Edsger W. Dijkstra 於 1956 年發明，當時他正在阿姆斯特丹和他的未婚妻一起購物，在咖啡休息的 20 分鐘內完成。
發明該演算法的原因是為了測試一臺名為 ARMAC 的新計算機。
迪傑斯特拉演算法
迪傑斯特拉演算法找到從一個頂點到所有其他頂點的最短路徑。
它透過反覆選擇最近的未訪問頂點，並計算到所有未訪問鄰居頂點的距離來實現。
迪傑斯特拉演算法通常被認為是解決最短路徑問題最直觀的演算法。
迪傑斯特拉演算法用於解決有向或無向圖的單源最短路徑問題。單源意味著選擇一個頂點作為起點，演算法將找出從該頂點到所有其他頂點的最短路徑。
迪傑斯特拉演算法不適用於帶有負權邊的圖。對於帶有負權邊的圖，可以使用下一頁描述的 Bellman-Ford 演算法代替。
為了找到最短路徑，迪傑斯特拉演算法需要知道哪個頂點是源點，需要一種方法來標記已訪問的頂點，並且需要了解它在圖中工作過程中到每個頂點的當前最短距離，並在找到更短的距離時更新這些距離。
工作原理
- 設定所有頂點的初始距離：源頂點的距離為 0，其他所有頂點的距離為無窮大。
- 選擇到起點距離最短的未訪問頂點作為當前頂點。因此，演算法總是以源頂點作為當前頂點開始。
- 對於當前頂點的每個未訪問鄰居頂點，計算到源頂點的距離，並在計算出的新距離更低時更新距離。
- 我們現在完成了對當前頂點的處理，因此將其標記為已訪問。已訪問的頂點不會再次被檢查。
- 返回步驟 2 以選擇新的當前頂點，並重復這些步驟，直到所有頂點都已訪問。
- 最後，我們得到了從源頂點到圖中每個其他頂點的最短路徑。
在上面的動畫中，當一個頂點被標記為已訪問時，該頂點及其邊會變淡，以表明迪傑斯特拉演算法已完成對該頂點的處理，並且不會再次訪問它。
注意： 此基本版本的迪傑斯特拉演算法提供了到每個頂點的最短路徑成本值，但沒有提供實際路徑。因此，例如，在上面的動畫中，我們得到到頂點 F 的最短路徑成本值為 10，但演算法並沒有告訴我們哪些頂點（D->E->C->D->F）構成了這條最短路徑。我們將在頁面下方新增此功能。
迪傑斯特拉演算法的詳細模擬
執行下面的模擬，以更詳細地瞭解迪傑斯特拉演算法如何在特定圖上執行，找出從頂點 D 到所有其他頂點的最短距離。
此模擬顯示瞭如何透過始終選擇離起點最近的未訪問頂點來計算從頂點 D 到所有其他頂點的距離。
請按照下面的分步說明，瞭解迪傑斯特拉演算法計算最短距離的所有詳細資訊。
手動演練
考慮以下圖。
我們要查詢從源頂點 D 到所有其他頂點的最短路徑，例如到 C 的最短路徑是 D->E->C，路徑權重為 2+4=6。
為了找到最短路徑，迪傑斯特拉演算法使用一個包含到所有其他頂點距離的陣列，並初始將這些距離設定為無窮大或一個非常大的數字。我們開始的頂點（源頂點）的距離設定為 0。
distances = [inf, inf, inf, 0, inf, inf, inf]
#vertices [ A , B , C , D, E , F , G ]
下圖顯示了從起始頂點 D 到其他頂點的初始無窮大距離。頂點 D 的距離值為 0，因為它是起點。
然後，迪傑斯特拉演算法將頂點 D 設定為當前頂點，並檢視到相鄰頂點的距離。由於到頂點 A 和 E 的初始距離是無窮大，因此到它們的距離被更新為邊權重。所以頂點 A 的距離從 inf 變為 4，頂點 E 的距離變為 2。正如前一頁所述，以這種方式更新距離值稱為“鬆弛”。
在鬆弛頂點 A 和 E 後，頂點 D 被視為已訪問，並且不會再次訪問。
下一個將被選為當前頂點的必須是到源頂點（頂點 D）距離最短的、之前未訪問過的頂點。因此，在頂點 D 之後，頂點 E 被選為當前頂點。
現在必須計算從 E 到所有相鄰且未訪問過的頂點的距離，並在需要時進行更新。
透過 E 到頂點 A 的計算距離為 2+4=6。但到頂點 A 的當前距離已經是 4，這更低，因此到頂點 A 的距離未更新。
到頂點 C 的距離計算為 2+4=6，這小於無窮大，因此到頂點 C 的距離已更新。
同樣，到節點 G 的距離被計算並更新為 2+5=7。
下一個要訪問的頂點是頂點 A，因為它在所有未訪問的頂點中到 D 的距離最短。
透過 A 到頂點 C 的計算距離為 4+3=7，這比到 C 的已設定距離更高，因此到 C 的距離未更新。
頂點 A 現在被標記為已訪問，下一個當前頂點是頂點 C，因為它在剩餘未訪問頂點中到 D 的距離最低。
頂點 F 的更新距離為 6+5=11，頂點 B 的更新距離為 6+2=8。
透過 C 到 G 的計算距離為 6+5=11，這比已設定的距離 7 更高，因此到 G 的距離未更新。
頂點 C 被標記為已訪問，下一個要訪問的頂點是 G，因為它在剩餘未訪問頂點中到 D 的距離最低。
頂點 F 已經有距離 11。這比從 G 計算出的距離 7+5=12 更低，因此到 F 的距離未更新。
頂點 G 被標記為已訪問，B 成為當前頂點，因為它在剩餘未訪問頂點中到 D 的距離最低。
透過 B 到 F 的新距離是 8+2=10，因為它比 F 的現有距離 11 更低。
頂點 B 被標記為已訪問，最後一個未訪問的頂點 F 沒有什麼需要檢查的了，因此迪傑斯特拉演算法完成。
每個頂點只被訪問一次，結果是從源頂點 D 到圖中每個其他頂點的最低距離。
迪傑斯特拉演算法的實現
為了實現迪傑斯特拉演算法，我們建立了一個 Graph 類。該 Graph 表示具有頂點和邊的圖。
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 3 行：我們建立 adj_matrix 來儲存所有邊和邊權重。初始值設定為 0。
第 4 行：size 是圖中頂點的數量。
第 5 行：vertex_data 儲存所有頂點的名稱。
第 7-10 行：add_edge 方法用於向頂點 v 新增從頂點 u 發出的邊，邊權重為 weight。
第 12-14 行：add_vertex_data 方法用於向圖中新增一個頂點。vertex 引數給出頂點應屬於的索引，而 data 是頂點的名稱。
該 Graph 類還包含執行迪傑斯特拉演算法的方法。
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances第 18-19 行：在 distances 陣列中，除起始頂點外，所有頂點的初始距離均設定為無窮大，起始頂點的距離為 0。
第 20 行：所有頂點最初均設定為 False，以在 visited 陣列中將它們標記為未訪問。
第 23-28 行：找到下一個當前頂點。將檢查從此頂點出發的邊，以檢視是否可以找到更短的距離。它是到起點距離最低的未訪問頂點。
第 30-31 行：如果未找到下一個當前頂點，則演算法完成。這意味著從源頂點可達的所有頂點都已訪問。
第 33 行：在鬆弛相鄰頂點之前，將當前頂點設定為已訪問。這更有效，因為我們避免了檢查到當前頂點本身的距離。
第 35-39 行：計算未訪問的相鄰頂點的距離，並在新計算出的距離更低時進行更新。
定義 Graph 類後，必須定義頂點和邊來初始化特定的圖，此迪傑斯特拉演算法示例的完整程式碼如下所示：
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0, 4) # D - A, weight 5
g.add_edge(3, 4, 2) # D - E, weight 2
g.add_edge(0, 2, 3) # A - C, weight 3
g.add_edge(0, 4, 4) # A - E, weight 4
g.add_edge(4, 2, 4) # E - C, weight 4
g.add_edge(4, 6, 5) # E - G, weight 5
g.add_edge(2, 5, 5) # C - F, weight 5
g.add_edge(2, 1, 2) # C - B, weight 2
g.add_edge(1, 5, 2) # B - F, weight 2
g.add_edge(6, 5, 5) # G - F, weight 5
# Dijkstra's algorithm from D to all vertices
print("\nDijkstra's Algorithm starting from vertex D:")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
print(f"Distance from D to {g.vertex_data[i]}: {d}")迪傑斯特拉演算法在有向圖上的應用
要在有向圖上執行迪傑斯特拉演算法，只需要進行很少的更改。
與我們在 有向圖的迴圈檢測 中所需的更改類似，我們只需刪除一行程式碼，即可使鄰接矩陣不再是對稱的。
讓我們來實現這個有向圖並從頂點 D 執行迪傑斯特拉演算法。
這是迪傑斯特拉演算法在有向圖上的實現，以 D 為源頂點。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0, 4) # D -> A, weight 5
g.add_edge(3, 4, 2) # D -> E, weight 2
g.add_edge(0, 2, 3) # A -> C, weight 3
g.add_edge(0, 4, 4) # A -> E, weight 4
g.add_edge(4, 2, 4) # E -> C, weight 4
g.add_edge(4, 6, 5) # E -> G, weight 5
g.add_edge(2, 5, 5) # C -> F, weight 5
g.add_edge(1, 2, 2) # B -> C, weight 2
g.add_edge(1, 5, 2) # B -> F, weight 2
g.add_edge(6, 5, 5) # G -> F, weight 5
# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
print(f"Shortest distance from D to {g.vertex_data[i]}: {d}")
下圖顯示了迪傑斯特拉演算法計算出的從頂點 D 到各頂點的最短距離。
此結果與之前在無向圖上使用迪傑斯特拉演算法的示例類似。但是，有一個關鍵區別：在這種情況下，頂點 B 無法從 D 訪問，這意味著到 F 的最短路徑現在是 11，而不是 10，因為路徑無法再透過頂點 B。
返回迪傑斯特拉演算法的路徑
透過一些調整，迪傑斯特拉演算法除了返回最短路徑值外，還可以返回實際的最短路徑。因此，例如，演算法不僅返回從頂點 D 到 F 的最短路徑值為 10，還可以返回最短路徑是“D->E->C->B->F”。
為了返回路徑，我們建立了一個 predecessors 陣列，以儲存每個頂點在最短路徑中的前一個頂點。predecessors 陣列可用於回溯以找到每個頂點的最短路徑。
示例
Python
class Graph:
# ... (rest of the Graph class)
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
predecessors[v] = u
return distances, predecessors
def get_path(self, predecessors, start_vertex, end_vertex):
path = []
current = self.vertex_data.index(end_vertex)
while current is not None:
path.insert(0, self.vertex_data[current])
current = predecessors[current]
if current == self.vertex_data.index(start_vertex):
path.insert(0, start_vertex)
break
return '->'.join(path) # Join the vertices with '->'
g = Graph(7)
# ... (rest of the graph setup)
# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances, predecessors = g.dijkstra('D')
for i, d in enumerate(distances):
path = g.get_path(predecessors, 'D', g.vertex_data[i])
print(f"{path}, Distance: {d}")
第 7 行和第 29 行：predecessors 陣列首先用 None 值初始化，然後隨著最短路徑值的更新，它會用每個頂點的正確前驅頂點進行更新。
第 33-42 行：get_path 方法使用 predecessors 陣列，並返回一個字串，其中包含從起始頂點到結束頂點的最短路徑。
迪傑斯特拉演算法與單個目標頂點
假設我們只對查詢兩個頂點之間的最短路徑感興趣，例如在下面的圖中查詢頂點 D 和頂點 F 之間的最短距離。
迪傑斯特拉演算法通常用於查詢從一個源頂點到圖中所有其他頂點的最短路徑，但也可以對其進行修改，使其僅查詢從源頂點到單個目標頂點的最短路徑，只需在到達（訪問）目標時停止演算法即可。
這意味著對於上圖中所示的特定圖，迪傑斯特拉演算法將在訪問 F（目標頂點）後停止，而在訪問頂點 H、I 和 J 之前停止，因為它們距離 D 比 F 更遠。
下面可以看到迪傑斯特拉演算法找到從 D 到 F 的最短距離並停止執行時計算出的距離狀態。
在上圖中，頂點 F 剛剛透過頂點 B 更新了距離 10。由於 F 是到 D 的距離最短的未訪問頂點，因此它通常會成為下一個當前頂點，但由於它是目標，因此演算法停止。如果演算法不停止，J 將是下一個獲得更新距離 11+2=13（來自頂點 I）的頂點。
下面的程式碼是實現迪傑斯特拉演算法以查詢到單個目標頂點的最短路徑。
示例
Python
class Graph:
# ... (existing methods)
def dijkstra(self, start_vertex_data, end_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
end_vertex = self.vertex_data.index(end_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None or u == end_vertex:
print(f"Breaking out of loop. Current vertex: {self.vertex_data[u]}")
print(f"Distances: {distances}")
break
visited[u] = True
print(f"Visited vertex: {self.vertex_data[u]}")
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
predecessors[v] = u
return distances[end_vertex], self.get_path(predecessors, start_vertex_data, end_vertex_data)
# Example usage
g = Graph(7)
# ... (rest of the graph setup)
distance, path = g.dijkstra('D', 'F')
print(f"Path: {path}, Distance: {distance}")
第 20-23 行：如果我們即將選擇目標頂點作為當前頂點並將其標記為已訪問，這意味著我們已經計算出了到目標頂點的最短距離，並且在這種單個目標情況下，迪傑斯特拉演算法可以停止。
迪傑斯特拉演算法的時間複雜度
設 \(V\) 為圖中頂點的數量，則迪傑斯特拉演算法的時間複雜度為
\[ O( V^2 ) \]
我們獲得此時間複雜度的原因是，必須搜尋距離最低的頂點以選擇下一個當前頂點，這需要 \(O(V)\) 時間。由於必須對連線到源的每個頂點執行此操作，因此我們需要考慮這一點，因此我們得到迪傑斯特拉演算法的時間複雜度為 \(O(V^2)\)。
透過使用最小堆或斐波那契堆資料結構來代替距離（本教程尚未解釋），搜尋最小距離頂點所需的時間從 \(O(V)\) 減少到 \(O(\log{V})\)，從而提高了迪傑斯特拉演算法的時間複雜度
\[ O( V \cdot \log{V} + E ) \]
其中 \(V\) 是圖中的頂點數，\(E\) 是圖中的邊數。
使用最小堆資料結構改進迪傑斯特拉演算法的時間複雜度對於擁有大型稀疏圖（即頂點數量多但邊數量不多）尤其有利。
使用斐波那契堆資料結構的迪傑斯特拉演算法實現更適合稠密圖，其中每個頂點都與幾乎所有其他頂點相連。
