在C語言中使用動態規劃求解最短路徑,可以按照以下步驟進行:
定義一個二維數組來表示圖中各個節點之間的距離。假設有n個節點,則可以定義一個n×n的二維數組dist[][],其中dist[i][j]表示節點i到節點j的距離。
初始化dist數組。對于直接相連的節點,賦予其對應的距離值;對于沒有直接連接的節點,可以將距離設為一個較大的值,表示不可達。
定義一個一維數組dp[]來保存最短路徑的值。其中dp[i]表示從起點到節點i的最短路徑長度。
初始化dp數組。將起點的最短路徑長度設為0,其他節點的最短路徑長度設為一個較大的值。
使用動態規劃的思想求解最短路徑。遍歷節點i,對于每個節點i,遍歷所有與其相連的節點j,更新dp[j]的值為dp[i] + dist[i][j],即通過節點i到達節點j的路徑長度。如果dp[j]的值被更新,則說明找到了一個新的最短路徑。
最終,dp數組中存儲的就是從起點到各個節點的最短路徑長度。
下面是一個使用動態規劃求解最短路徑的示例代碼:
#include <stdio.h>
#define INF 99999
void shortestPath(int graph[][4], int n, int src) {
int dist[n];
// 初始化距離數組
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
dist[src] = 0; // 起點到自身的距離為0
// 動態規劃求解最短路徑
for (int k = 0; k < n - 1; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i] + graph[i][j] < dist[j]) {
dist[j] = dist[i] + graph[i][j];
}
}
}
}
// 輸出最短路徑
printf("最短路徑長度:\n");
for (int i = 0; i < n; i++) {
printf("%d -> %d: %d\n", src, i, dist[i]);
}
}
int main() {
int graph[4][4] = { {0, 2, INF, 1},
{INF, 0, 4, INF},
{INF, INF, 0, 6},
{INF, INF, INF, 0} };
shortestPath(graph, 4, 0);
return 0;
}
在上述示例代碼中,我們使用一個4×4的二維數組graph[][]來表示圖中各個節點之間的距離。INF表示不可達的情況。
執行該代碼,將輸出從起點0到其他節點的最短路徑長度。