使用C語言實現迪杰斯特拉算法進行路徑規劃

迪杰斯特拉算法是一種用于尋找加權圖中最短路徑的經典算法。它特別適合用于計算從一個起點到其他所有節點的最短路徑，前提是圖中的邊權重為非負數。

---

一、迪杰斯特拉算法的基本原理

迪杰斯特拉算法的核心思想是“貪心法”，即每一步都選擇當前最優解。具體步驟如下：

1. 初始化：設定起點到自身的距離為0，其他節點的距離為無窮大（表示尚未可達）。
2. 選擇節點：從未訪問的節點中選擇距離起點最近的節點。
3. 更新距離：通過該節點，嘗試更新其鄰居節點的最短路徑距離。
4. 重復步驟：重復選擇和更新，直到所有節點都被訪問。

---

二、C語言實現迪杰斯特拉算法

在C語言中實現迪杰斯特拉算法，我們需要用到數組來存儲節點之間的距離和路徑信息。以下是一個簡單的實現示例：

1. 準備工作

首先，我們需要定義一些常量和數據結構：

#include <stdio.h>
#include <limits.h> // 用于定義無窮大#define V 5 // 圖中節點的數量// 找到未訪問節點中距離最小的節點
int minDistance(int dist[], int visited[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++) {if (visited[v] == 0 && dist[v] <= min) {min = dist[v];min_index = v;}}return min_index;
}// 打印從起點到各節點的最短距離
void printSolution(int dist[]) {printf("節點 \t 距離\n");for (int i = 0; i < V; i++) {printf("%d \t %d\n", i, dist[i]);}
}

2. 迪杰斯特拉算法實現

接下來，我們實現迪杰斯特拉算法的核心部分：

void dijkstra(int graph[V][V], int src) {int dist[V]; // 存儲從起點到各節點的最短距離int visited[V]; // 標記節點是否已訪問// 初始化所有距離為無窮大，所有節點未訪問for (int i = 0; i < V; i++) {dist[i] = INT_MAX;visited[i] = 0;}// 起點到自身的距離為0dist[src] = 0;// 找到從起點到所有節點的最短路徑for (int count = 0; count < V - 1; count++) {int u = minDistance(dist, visited); // 選擇距離最小的未訪問節點visited[u] = 1; // 標記為已訪問// 更新鄰居節點的距離for (int v = 0; v < V; v++) {if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}// 打印結果printSolution(dist);
}

3. 測試算法

最后，我們用一個簡單的圖來測試算法：

int main() {// 圖的鄰接矩陣表示int graph[V][V] = {{0, 10, 0, 0, 5},{0, 0, 1, 0, 2},{0, 0, 0, 4, 0},{7, 0, 6, 0, 0},{0, 3, 9, 2, 0}};// 從節點0開始計算最短路徑dijkstra(graph, 0);return 0;
}

---

三、運行結果

運行上述代碼后，程序將輸出從起點（節點0）到其他節點的最短路徑距離：

節點     距離
0        0
1        8
2        9
3        7
4        5

這表示從節點0到節點1的最短距離是8，到節點2是9，依此類推。

---

這個算法在處理加權圖的最短路徑問題時非常高效，尤其適用于權值為非負的情況。在實際應用中，迪杰斯特拉算法可以用于導航系統、網絡路由優化等場景。