給定一個有向加權圖，它有 m 個邊和 n 個頂點。每條邊的權重都是非負的。頂點要么在集合 S1 中，要么在集合 S2 中（S1 和 S2 不相交）。您需要找到任意對(v1, v2) 之間的最短路徑（v1 在 S1 中，v2 在 S2 中）。
解決方案的運行時間應該是O(mlogn)。
' Nonnegtive ' 和 ' mlogn ' 讓我想起了Dijkstra，但我不知道如何在恒定時間內使用 Dijkstra 來解決它。
提前致謝。
uj5u.com熱心網友回復：
Dijkstra，但已修改：
初始化
double min = infinite; // shortest distance between n1 (of s1) and n2 (of s2) Node n1 = null, n2 = null; // members of s1 and s2 with shortest distance between them Set<Node> visited = new Set<>(); // initially-empty set of visited nodes of s1從 s1 的每個節點運行 Dijkstra直到
一種。您到達 s2 的節點（將開始節點添加到
visited; if 、distance < minupdate和）minn1n2灣。您到達已經存在的 s1 節點
visited（將起始節點添加到visited）C。您用完了要訪問的節點（僅當圖形未連接時才有可能；將起始節點添加到
visited）回傳結果對。
運行 Dijkstra 是O(m log n)最壞的情況，但您不會完全運行它|s1|- 相反，上述步驟的最終結果與每個連接組件僅完全運行一次 Dijkstra 相同或更快（就訪問的邊緣而言）。因此，整個演算法為O(m log n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/466752.html