ipad 建網(wǎng)站免費(fèi)搜索引擎入口
編程要求
在圖的應(yīng)用中，有一個(gè)很重要的需求：我們需要知道從某一個(gè)點(diǎn)開始，到其他所有點(diǎn)的最短路徑。這其中，Dijkstra 算法是典型的最短路徑算法。
本關(guān)的編程任務(wù)是補(bǔ)全右側(cè)代碼片段中 Begin 至 End 中間的代碼，實(shí)現(xiàn) Dijkstra 算法求單源最短路徑，具體要求如下：
補(bǔ)全代碼 int[] Paths(int source) 方法，實(shí)現(xiàn) Dijkstra 算法；
輸出源點(diǎn) source 到其他各個(gè)定點(diǎn)的距離，如果不可達(dá)，則距離輸出 INF。
測(cè)試舉例
測(cè)試過程：
平臺(tái)將創(chuàng)建用戶補(bǔ)全后的ShortestPath類的對(duì)象；
調(diào)用對(duì)象的addEdge(int u, int v, int w)方法，添加邊和邊的權(quán)重信息，構(gòu)建圖G；
調(diào)用對(duì)象的Paths(int source)方法執(zhí)行Dijkstra算法，求最短路徑，并輸出返回的最短路徑，這里源點(diǎn)設(shè)置為1；
接著根據(jù)程序的輸出判斷程序是否正確。
以下是測(cè)試樣例：
測(cè)試輸入：
5 7
1 2 8
1 3 1
1 4 2
3 4 2
2 4 3
3 5 3
4 5 3
(5 和 7 分別表示頂點(diǎn)數(shù)和邊數(shù))
預(yù)期輸出：
0 5 1 2 4?
思路解析：
? ? ? ? 求單源最短路徑就是求一個(gè)點(diǎn)到除它以外所有點(diǎn)的最短距離，首先我們還是用鄰接矩陣來儲(chǔ)存圖的信息。以測(cè)試輸入為例，示意圖如下。
? ? ? ??既然是求1的單源最短路徑，那我們就定義一個(gè)數(shù)組dic[n+1],將dic初始化存儲(chǔ)從1到所有點(diǎn)的直接距離。比如dic[1]到dic[5]分別是【0，8，1，2，99999999】，因?yàn)?無法直接到5，所以初始化為99999999。
? ? ? ? 然后找出dic里面1到2-n之間的最短距離，發(fā)現(xiàn)是dic[3] = 1,然后找1通過3能到達(dá)的地方，發(fā)現(xiàn)能到達(dá)4和5，如果1通過3到達(dá)4的話，得出dic[4] = 2 < dic[3]+arr[3][4] = 3，無法使到四的路程更短，所以不改變dic[4]的值，但是我們發(fā)現(xiàn)到達(dá)5，即dic[5] = 99999999>dic[3]+arr[3][5] = 4,能使1到5距離縮短，于是改變dic[5]的值。這樣我們就得到能通過3進(jìn)行優(yōu)化一輪路徑，學(xué)術(shù)名叫做松弛。
????????
? ? ? ? 我們知道，如果已經(jīng)通過3實(shí)現(xiàn)了一輪優(yōu)化，那么我們將進(jìn)一步縮短路程的話，是不能走回頭路的，因?yàn)槿绻俅谓?jīng)過3的話沒有意義，所以最短路沒有重復(fù)路徑。
? ? ? ? 那么我們就要定義一個(gè)數(shù)組來存儲(chǔ)已經(jīng)作為轉(zhuǎn)點(diǎn)進(jìn)行一輪松弛的點(diǎn)，我們可以定義book[n+1]來存儲(chǔ)。將作為轉(zhuǎn)點(diǎn)的點(diǎn)比如3，用book[3] = 1，表示已經(jīng)使用過。
? ? ? ? 之后便是重復(fù)步驟，找除去dic[3]以外的最小值，也就是dic[4],繼續(xù)進(jìn)行一輪松弛，將4這個(gè)點(diǎn)用book[4] = 1,表示已經(jīng)使用過。
? ? ? ? 之后的圖大家可以自己試著來畫出。
具體代碼：
#include<stdio.h>
int main(void)
{
? ? int arr[100][100] = { 0 };
? ? int dic[100];
? ? int book[100] = { 0 };
? ? int m, n, a, b, c, u, v;
? ? int inf = 99999999;
? ? scanf("%d%d", &n, &m);
? ? for (int i = 1; i <= n; i++)
? ? ? ? for (int j = 1; j <= n; j++)
? ? ? ? ? ? if (i == j)
? ? ? ? ? ? ? ? arr[i][j] = 0;
? ? ? ? ? ? else
? ? ? ? ? ? ? ? arr[i][j] = inf;
? ? for (int i = 1; i <= m; i++)
? ? {
? ? ? ? scanf("%d%d%d", &a, &b, &c);
? ? ? ? arr[a][b] = c;
? ? ? ? arr[b][a] = c;
? ? }//無向圖初始化。
? ? for (int i = 1; i <= n; i++)
? ? ? ? dic[i] = arr[1][i];//初始化dic數(shù)組
?
? ? for (int i = 1; i <= n - 1; i++)//最多要進(jìn)行n-1輪松弛，i值不會(huì)使用，僅僅表示循環(huán)多少輪。
? ? {
? ? ? ? int min = inf;
? ? ? ? for (int j = 2; j <= n; j++)
? ? ? ? {
? ? ? ? ? ? if (book[j] == 0 && dic[j] < min)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? min = dic[j];
? ? ? ? ? ? ? ? u = j;
? ? ? ? ? ? }
? ? ? ? }//找出從1到任意數(shù)字的最短值。
? ? ? ? book[u] = 1;//將該位置提前存儲(chǔ)，表示已經(jīng)使用過。
? ? ? ? for (v = 2; v <= n; v++)//優(yōu)化1通過u到所有點(diǎn)的路徑。
? ? ? ? {
? ? ? ? ? ? if (arr[u][v] < inf)//如果u到v沒有通路，也就沒辦法優(yōu)化。
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (dic[v] > dic[u] + arr[u][v])
? ? ? ? ? ? ? ? ? ? dic[v] = dic[u] + arr[u][v];//優(yōu)化賦值過程。
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? for (int i = 1; i <= n; i++)
? ? ? ? printf("%d ", dic[i]);//打印結(jié)果。
? ? return 0;
}
注意：
? ? ? ? 實(shí)際上迪杰斯特拉算法可以看作是貪心算法，通過每一步的最優(yōu)解組合成全局最優(yōu)解，感興趣的同學(xué)們可以去網(wǎng)上查找關(guān)于貪心算法的知識(shí)，這種類型的題目我們以后也會(huì)分享。