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

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

1c:2

2c:2f:6

3c:2f:6e:10

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

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

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

初始化d[i]是無(wú)限的。因?yàn)樗鼜腣4開(kāi)始，所以D4=0并且選擇了標(biāo)記V4。

接下來(lái)，我們開(kāi)始Dijkstra算法：

連接到V4的未標(biāo)記點(diǎn)是V2和V6。這樣，我們更新D2=20，D6=15，選擇所有未標(biāo)記點(diǎn)中最小的點(diǎn)，D6=15，并且選擇了標(biāo)記V6。這樣，我們計(jì)算V4->V6的最短距離，D6=15；

從V6開(kāi)始，連接到V6的未標(biāo)記點(diǎn)是V2，然后計(jì)算D6=21>20，所以不更新D2，選擇所有未標(biāo)記點(diǎn)中最小的D2=20，標(biāo)記V2已被選中，所以V4->v2的最短距離，D2=20；

從V2開(kāi)始，V1和V5與V2連接且未標(biāo)記，D1=D2，10=30，D5=D2 30=50，選擇所有未標(biāo)記點(diǎn)中的最小點(diǎn)，D1=30，標(biāo)記V1已選中，因此我們計(jì)算V4->v1的最短距離，D1=30；

從V1開(kāi)始，V3與V1連接且未標(biāo)記，D3=D1 15=45，在所有剩余未選點(diǎn)中選擇最小的D3=45（D5=50），標(biāo)記V3已被選中，因此我們計(jì)算V4->v3的最短距離，D3=45

從V3開(kāi)始，沒(méi)有路徑輸出，不更新距離，在所有剩余未選點(diǎn)中選擇最小的D5=50，標(biāo)記V5已被選中，所以我們計(jì)算最短距離V4->v5，D5=50。

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

注意：已選擇上述標(biāo)記點(diǎn)。注意：在算法的實(shí)現(xiàn)中，所有的點(diǎn)都被放入隊(duì)列中。一旦選擇了一個(gè)點(diǎn)，即計(jì)算了最短距離，該點(diǎn)將從隊(duì)列中刪除，直到隊(duì)列為空。我寫(xiě)這個(gè)標(biāo)記只是為了便于理解。

希望能幫助您清楚地了解圖論中最重要的算法之一Dijkstra算法。