假設我有一個加權的、無向的、無環圖，沒有負值權重，由 n 個頂點和 n-1 條邊組成。如果我想計算每一個之間的總距離（使用邊緣權重）然后將其相加，我應該使用哪種演算法？例如，如果一個圖有 4 個頂點，像 ab、ac、cd 一樣連接，那么程式應該輸出從 ad、ac、ab、bc、bd 等開始所需的總距離。您可以將其稱為給定頂點之間的所有可能路徑。我使用的語言是 C 。
我試過使用 Dijikstra 和 Prim 的演算法，但沒有一個對我有用。我考慮過使用普通或多源 DFS，但我已經為此苦苦掙扎了一段時間。真的有一種快速的計算方法嗎，還是我完全誤解了這個問題？
uj5u.com熱心網友回復：
由于您有一個無環圖，因此任意兩點之間只有一條可能的路徑。這使計算變得更簡單，并且您不需要使用任何真正的尋路演算法。
假設我們有一條連接節點 A 和 B 的邊 E。計算從節點 A 可以到達多少個節點，而不使用邊 E（包括 A）。將其乘以從節點 B 可以到達的節點數，而不使用邊 E（包括 B）。現在你有了通過邊 E 的路徑數。將它乘以邊 E 的權重，你就得到了邊 E 對總和的總貢獻。
對每條邊做同樣的事情并將結果相加。
為了使演算法更高效，每條邊都可以存盤快取值，這些值表示邊的每一側可到達的節點數。
您不必使用深度優先搜索。下面是一些偽代碼，展示了如何利用快取非常快速地計算邊緣 E 一側可到達的節點數：
int count_nodes_reachable_on_edge_side(Edge e, Node a) {
// assume edge e directly connects to node a
if (answer is already cached in e) { return the answer; }
answer = 1; // a is reachable
for each edge f connected to node a {
if (f is not e) {
let b be other node f touches (not a)
answer = count_nodes_reachable_on_edge_side(f, b)
}
}
cache the answer in edge e;
return answer;
}
uj5u.com熱心網友回復：
我已經在我的另一個答案中提出了一個 O(N^2) 演算法，但我認為你實際上可以用這個偽代碼在 O(N) 時間內完成這個：
let root be an arbitrary node on the graph;
let total_count be the total number of nodes;
let total_cost be 0;
process(root, null);
// Returns the number of nodes reachable from node n without going
// through edge p. Also adds to total_cost the contribution from
// all edges touching node n, except for edge p.
int process(Node n, Edge p)
{
count = 1
for each edge q that touches node n {
if (q != p) {
let m be the other node connected to q (not n)
sub_count = process(m, q)
total_cost = weight(q) * sub_count * (total_count - sub_count)
count = sub_count
}
}
return count
}
它的運行時間是 O(N)，其中 N 是節點數，因為process每個節點都將被呼叫一次。
（對于注重細節的讀者：內部回圈process并不重要：有 O(N) 次迭代呼叫process，因為process在每個節點上只呼叫一次。有 O(N) 次迭代不做任何事情（因為q == p） ，因為這些迭代只能在process呼叫時發生一次。）
每條邊也將被訪問。在我們遞回地統計邊的一側的節點數之后，我們可以做一個簡單的減法（total_count - sub_count）來得到邊的另一側的節點數。當我們有這兩個節點數時，我們可以將它們相乘以獲得通過邊的路徑總數，然后將其乘以權重，并將其添加到總成本中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/537623.html