資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究為什麼 Dijkstra 演算法在負權重情況下會失效？
簡介
Dijkstra 演算法是一種廣泛使用的圖遍歷演算法，用於查詢圖中兩個頂點之間的最短路徑。它高效且在處理非負權重圖時能保證最佳結果。但是，當引入負權重時，Dijkstra 演算法將無法產生正確的結果。在本文中，我們將探討其失效的原因，並討論使用 C 語言處理圖中負權重的三種不同方法。我們將對每種方法進行逐步說明，並附帶相應的程式碼和輸出。
理解 Dijkstra 演算法
Dijkstra 演算法透過迭代地擴充套件從源頂點到圖中所有其他頂點的最短路徑來工作，直到到達目標頂點。它維護一個待處理頂點的集合，稱為“未訪問集合”，並跟蹤從源到每個頂點的已知最短距離。
最初，到源頂點的距離設定為零，所有其他距離設定為無窮大。隨著演算法的進行，它選擇未訪問集合中距離最小的頂點，檢查其相鄰頂點，如果找到更短的路徑，則更新其距離。此過程持續進行，直到到達目標頂點或沒有更多頂點可訪問。
負權重的問題
Dijkstra 演算法中負權重最主要的問題在於，它假設到達任何給定頂點的最短路徑總是透過按從源到頂點的距離遞增順序訪問頂點來找到的。然而，當引入負權重時，這個假設就會失效，導致結果不準確。
為了理解為什麼會發生這種情況，讓我們考慮一個 Dijkstra 演算法失效的例子。假設我們有一個包含三個頂點的圖：
A、B 和 C 連線如下：A →(-1)→ B →(-2)→ C
假設源頂點是 A，Dijkstra 演算法最初會將到 B 的距離設定為 -1，將到 C 的距離設定為無窮大。但是，當我們考慮權重為 -2 的從 B 到 C 的邊時，該演算法將錯誤地將到 C 的距離更新為 -3，認為路徑 A → B → C 比當前路徑 A → C 更短。
該演算法未能識別 -2 的負權重進一步減少了從 B 到 C 的距離，使得路徑 A → C 比 A → B → C 更短。這種不正確的更新導致最短路徑計算錯誤。
C語言程式碼實現
現在讓我們看一下 Dijkstra 演算法在 C 語言中的程式碼實現，重點是它在遇到負權重時的侷限性。
示例
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define G 4
int short_dst(int dt[], bool visited[]) {
int min = INT_MAX, x;
for (int t = 0; t < G; t++)
if (visited[t] == false && dt[t] < min)
min = dt[t], x = t;
return x;
}
void dkst(int graph[G][ G], int src) {
int dist[G];
bool visited[G];
for (int i = 0; i < G; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[src] = 0;
for (int count = 0; count < G - 1; count++) {
int u = short_dst(dist, visited);
visited[u] = true;
for (int t = 0; t < G; t++) {
if (!visited[t] && graph[u][t] && dist[u] != INT_MAX && dist[u] + graph[u][t] < dist[t])
dist[t] = dist[u] + graph[u][t];
}
}
printf("V\t Distance from Source\n");
for (int i = 0; i < G; i++)
printf("%d\t%d\n", i, dist[i]);
}
int main() {
int graph[G][ G] = {{0, 1, INT_MAX, INT_MAX},
{INT_MAX, 0, INT_MAX, INT_MAX},
{INT_MAX, INT_MAX, 0, -2},
{INT_MAX, INT_MAX, INT_MAX, 0}};
dkst(graph, 0);
return 0;
}
輸出
V Distance from Source 0 0 1 1 2 -2147483648 3 -2147483648
結論
Dijkstra 演算法是查詢具有非負權重的圖中最短路徑的高效且可靠的演算法。但是，當圖包含負權重時，它將無法產生精確的結果。該演算法在處理負權重時所做的不正確假設會導致錯誤的最短路徑計算。雖然 Dijkstra 演算法在處理負權重方面存在侷限性，但在顯示非負權重的場景中，它仍然是一個重要的工具。透過理解其失效的原因並研究替代演算法（如 Bellman-Ford 演算法），我們可以在選擇最合適的演算法來解決圖相關問題時做出明智的選擇，從而確保在各個領域都能獲得效率和準確的結果。
瀏覽量：317
