Dijkstra環狀樹

Question

任何人都知道嗎？

一個循環樹是一個加權的有向圖，它是從二叉樹 中通過向每個葉子的根部添加一條邊來構建的。每個邊緣都有一個非負重量的 。

1. 多少時間Dijkstra算法需要計算了有n個節點 一個環形樹的兩個頂點u和v之間的最短路徑？
2. 描述和分析一個更快的算法。

Answer 1

多少時間Dijkstra算法需要計算了有n個節點 一個環形樹的兩個頂點u和v之間的 最短路徑？

這將需要O(VlogV)時間（最壞情況分析）。
請注意，對於連接u到v的每個節點對(u,v)都有一條簡單路徑。如果這條路徑由於某種原因包含非常重的加權邊緣，那麼Dijksta的算法會持續推遲這個邊緣，並且直到它將會發現正確的路由，這將使算法必須發現大部分頂點使得複雜度爲O(VlogV)（請注意，對於此圖，E在O(V)中）。

描述和分析一個更快的算法。

由於有一個簡單的路徑，你只需要找到它。
可以通過在樹中找到lowest common ancestor（無循環），然後從u找到到此祖先的路由，從而輕鬆完成。
該算法的複雜性是O(h) - 其中h是圖形的高度。

Answer 2

我認爲amit的答案是錯誤的。

在描述和分析一個更快的算法。

您無法從O（h）中找到從頂點u到此祖先的最便宜的路線，因此，此算法不是O（h）。出於兩個原因，如果內部節點只有父節點到子節點的邊緣，我們需要向下看，以找到到最常見的祖先（或根節點）的最便宜的路線，而且我不知道可以這樣做的算法。第二個原因，如果存在父 - >子和父 - >父邊，那麼從源頂點到最低公共頂點的路徑可以通過任何內部樹節點（頂點）的3個相鄰頂點或1個相鄰頂點根）任何葉節點頂點，因此我們不能在O（h）中完成。

根據我對問題的理解，child-> parent edge不在循環樹圖的定義中。因此，我們唯一的目標就是走下去，回到頂端，從根到目標是一條簡單的單一路徑。因此，我們將問題簡化爲找到從根到最便宜的路線，從而降低複雜性。此外，如果目標是源的直接後代，那麼我們將在查找最便宜的根路徑時停止搜索。如果源是根，那麼問題就很簡單，因爲路由是沿着目標子樹沿從根到目標的簡單單一路徑。