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

試?yán)肈ijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(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]是無限的。因為它從V4開始，所以D4=0并且選擇了標(biāo)記V4。

接下來，我們開始Dijkstra算法：

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

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

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

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

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

此時，所有點都被訪問，結(jié)束。

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

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