試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)？1 c:22 c:2 f:63 c:2 f:6 e:104 c:2 f:6 e:10 d:115 c:2

試?yán)肈ijkstra算法求圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)？

1 c:2

2 c:2 f:6

3 c:2 f:6 e:10

4 c:2 f:6 e:10 d:11

5 c:2 f:6 e:10 d:11 g:14

6 c:2 f:6 e:10 d:11 g:14 b:15

(用Dijkstra算法)求出圖中頂點(diǎn)1到其余各頂點(diǎn)的最短路徑？

我用自己寫的軟件運(yùn)行了一下，只截圖頂點(diǎn)1到頂點(diǎn)8吧，橙色線就是最短路徑了。 其實(shí)從圖就不難看出答案，1-5-6-7-4-8。這也是1到各頂點(diǎn)5，6，7，4，8的各點(diǎn)最短路徑。 如果頂點(diǎn)1到頂點(diǎn)3就是1-5-6-7-3.

利用Dijkstra算法求下圖中從頂點(diǎn)1到其它各頂點(diǎn)間的最短路徑，按下面表格形式？

初始化d[i]為無窮大，由于從v4開始，所以將d4=0，標(biāo)記v4已選擇。

下面開始Dijkstra算法：

和v4相連的且未標(biāo)記的點(diǎn)有v2和v6，這樣更新d2=20，d6=15，選擇未標(biāo)記所有點(diǎn)中最小的d6=15，標(biāo)記v6已選擇，這樣我們算出了v4->v6最短距離d6=15；

從v6開始，和v6相連的且未標(biāo)記的是v2，此時(shí)算d6 6=21>20，所以不更新d2，選擇未標(biāo)記所有點(diǎn)中最小的d2=20，標(biāo)記v2已選擇，這樣算出了v4->v2最短距離d2=20；

從v2開始，和v2相連的且未標(biāo)記的有v1和v5，d1=d2 10=30，d5=d2 30=50，選擇未標(biāo)記所有點(diǎn)中最小的d1=30，標(biāo)記v1已選擇，這樣我們算出了v4->v1最短距離d1=30；

從v1開始，和v1相連的且未標(biāo)記的有v3，d3=d1 15=45，選擇剩下沒被選的所有點(diǎn)的最小的d3=45(d5=50)，標(biāo)記v3已選擇，這樣我們算出了v4->v3最短距離d3=45

從v3開始，沒有出去的路徑，不更新距離，選擇剩下沒被選的所有點(diǎn)的最小的d5=50，標(biāo)記v5已選擇，這樣我們算出了v4->v5最短距離d5=50.

此時(shí)所有的點(diǎn)都被訪問，結(jié)束。

注：上面的標(biāo)記點(diǎn)已選擇注意下，在算法的實(shí)現(xiàn)中用的是將所有的點(diǎn)放入隊(duì)列中，一旦一個(gè)點(diǎn)被選擇就是說求出了最短距離，就從此隊(duì)列刪除該點(diǎn)，一直到此隊(duì)列為空，結(jié)束算法，我寫標(biāo)記只是為了方便理解。

希望能幫你清晰了解Dijkstra算法，圖論中很重要的算法之一。