single-sourceshortestpaths-資料下載頁(yè)
2025-07-17 17:11本頁(yè)面
【正文】 ∞ 0 5 3 2 6 (g) s 5 2 7 1 2 6 1 3 4 2 SingleSource Shortest Paths 24 Dijkstra演算法 ? 僅能處理無(wú)負(fù)邊的圖。 ? 比 Bellmanford演算法快，也是藉由挑選特定順序來(lái)做 Relaxation來(lái)達(dá)成目的。 ? 利用 Priority queue來(lái)實(shí)做。 ? 主要關(guān)鍵想法：利用收斂性質(zhì)。 SingleSource Shortest Paths 25 Dijkstra演算法 Q: Priority queue with d as the key Dijkstra(G,w,s) { InitializeSingleSource(G,s) Q=V[G] while Q is not empty do u=ExtractMin(Q) for each v∈adj[u] do Relax(u,v,w) } SingleSource Shortest Paths 26 Dijkstra演算法操作範(fàn)例 0 ∞ ∞ ∞ ∞ 10 5 1 2 3 2 7 9 4 6 (a) 0 10 ∞ 5 ∞ 10 5 1 2 3 2 7 9 4 6 (b) s s SingleSource Shortest Paths 27 Dijkstra演算法操作範(fàn)例 0 8 11 5 7 10 5 1 2 3 2 7 9 4 6 (d) s 0 8 14 5 7 10 5 1 2 3 2 7 9 4 6 (c) s SingleSource Shortest Paths 28 Dijkstra演算法操作範(fàn)例 0 8 9 5 7 10 5 1 2 3 2 7 9 4 6 (e) 0 8 9 5 7 10 5 1 2 3 2 7 9 4 6 (e) s s SingleSource Shortest Paths 29 Dijkstra演算法分析 ? 依照使用的 Priority queue實(shí)做方式不同，會(huì)有不同的執(zhí)行時(shí)間。 ? 使用 Linear array來(lái)實(shí)做，消耗 O(|V|2)的時(shí)間。 ? 使用 Binary heap來(lái)實(shí)做，消耗 O(|E|log|V|)的時(shí)間。 ? 使用 Fibonacci heap來(lái)實(shí)做，消耗 O(|E|+|V|log|V|)的 時(shí)間。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1