有向圖d演算法

① 用來求解加權有向圖的最短路徑的演算法是什麼演算法

單元最短路徑：
1.如果沒有負權環的稀疏圖，可以用SPFA，時間復雜度O（KM）
M是邊數，K是平均入隊列的次數
2.如果沒有負權環的稠密圖，建議用Dijkstra O（N^2），用二叉堆可優化到
O（NlogN），斐波那契堆編程復雜度太高，不易於實現
3.如果有負權環，可以嘗試floyd,O(n^3)

任兩點最短路徑：floyd較好實現，基於重標號johnson也不錯（稀疏圖效率高）
具體程序可以上網查

② 已知帶權有向圖如圖7-29所示,請利用Dijkstra演算法從頂點V4出發到其餘頂點的最短路

初始化d[i]為無窮大，由於從v4開始，所以將d4=0，標記v4已選擇。
下面開始Dijkstra演算法：
和v4相連的且未標記的點有v2和v6，這樣更新d2=20，d6=15，選擇未標記所有點中最小的d6=15，標記v6已選擇，這樣我們算出了v4->v6最短距離d6=15；
從v6開始，和v6相連的且未標記的是v2，此時算d6+6=21>20,所以不更新d2，選擇未標記所有點中最小的d2=20，標記v2已選擇，這樣算出了v4->v2最短距離d2=20；
從v2開始，和v2相連的且未標記的有v1和v5，d1=d2+10=30,d5=d2+30=50，選擇未標記所有點中最小的d1=30，標記v1已選擇，這樣我們算出了v4->v1最短距離d1=30；
從v1開始，和v1相連的且未標記的有v3，d3=d1+15=45，選擇剩下沒被選的所有點的最小的d3=45(d5=50)，標記v3已選擇，這樣我們算出了v4->v3最短距離d3=45
從v3開始，沒有出去的路徑，不更新距離，選擇剩下沒被選的所有點的最小的d5=50，標記v5已選擇，這樣我們算出了v4->v5最短距離d5=50.
此時所有的點都被訪問，結束。
註：上面的標記點已選擇注意下，在演算法的實現中用的是將所有的點放入隊列中，一旦一個點被選擇就是說求出了最短距離，就從此隊列刪除該點，一直到此隊列為空，結束演算法，我寫標記只是為了方便理解。
希望能幫你清晰了解Dijkstra演算法，圖論中很重要的演算法之一。