有向邊的加權邊圖及其權重的算法

Question

我有一個邊有非負權的有向圖。

我的算法，應該做到以下幾點：。

• 獲得從頂點的所有路徑u到頂點v
• 計算每個路徑上的最小加權邊緣從u到v
• 計算最大的我從上面計算出的最小加權邊。

什麼算法對此有好處？我問這個，因爲我可以天真地執行上面的步驟，因爲我已經說過了（蠻力）。

我有一種感覺，這是對Dijkstra算法的輕微修改，但我不確定。另外，時間複雜度是多少？

Answer 1

實際上考慮從u到v的所有路徑的任何算法都將花費指數時間，因爲存在指數數量的這樣的路徑 - 考慮梯子或2N個節點的網格 - 從一端或另一端進入從長遠來看，你至少有N個獨立的選擇，所以至少有2^N個可能的路徑。

我想你可以修改Dijkstra的算法來做到這一點。在https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode有psuedocode。作爲第一個修改，將第6行更改爲將所有初始距離設置爲零。我們需要考慮不變量，並且我們的第一個不變量可以是dist [v]是到v的路徑中的最小邊的最大值，對於迄今爲止看到的所有路徑。和之前一樣，我們將prev [v]設置爲undefined並將v添加到Q，該隊列包含當前正在考慮的所有節點。作爲初始化的最後一部分，我們設置dist [source] = infinity - 不是0.您可以將其視爲hack，或者作爲定義從v到v的長度爲0的路徑中的最小邊長度的一種方式，沒有任何邊緣。

現在我們已經知道Q包含所有節點，其中最小邊的最大值仍在考慮之中，並且所有這些節點的這個值只會增加。現在我們從dist中刪除最大值爲dist [u]的節點u - 這是第13步，修改爲min，將其更改爲max。對於u的每個鄰居v，我們計算min（dist [v]，length（u，v））。這是沿着從源到u的任何路徑的最大可能最小邊緣長度的新候選，所以如果這個距離大於dist [u]，我們將dist [u]設置爲該值。請注意，這意味着對於我們剛刪除的Q的元素v，Q中沒有任何元素u會將dist [u]設置爲大於dist [v]的值，這是隊列中的最大值那時候。這意味着，一旦我們從隊列中移除了一個元素v，其值dist [v]就已經計算好了，並且不能通過任何後續計算來增加。請注意，我們剛剛在隊列Q中爲節點更改了dist [u]。如果使用優先級隊列等數據結構實現Q，則這可能意味着實現將不得不從舊的優先級隊列中刪除u dist [u]的值，然後將其重新插入dist [u]的新值中。

正確性來自不變量 - 每次我們都有dist [v]沿着每條路徑的最小邊沿的最大值，當我們從隊列中移除v時，我們知道 - 因爲它有一個最大值一切仍在隊列中 - 我們可以考慮的其他路徑都不可能改變這個值。

這樣做的時間與Dijkstra相同，原因相同。我們在開始時將每個元素輸入到隊列中，並且一次從隊列中移除每個元素。這告訴我們在第14行執行刪除操作的次數。

（最小加權邊緣的最高似乎是一個奇怪的事情來計算 - 是有一個有趣的應用程序在這裏，還是這是一個人爲的練習，讓你去想Dijkstra算法）

Answer 2

我覺得我們不」在這裏需要迪傑克斯特拉。假設我們選擇了具有期望的最小邊緣的路徑。它顯然不包括重量較輕的邊。因此，該算法是

• 挑K最厚邊
• 使用DFS/BFS檢查v可達來自u通過這個邊緣（f(K) is true）
• 如果K1>K2和f(K2) is true，那麼顯然f(K1) is true
• 所以我們可以通過K來運行二進制搜索

時間複雜度是O((N+M) log M)其中N - 頂點數和M - 邊數