我有這個問題上形成算法的塞奇威克的課程：「臨界邊緣給定一個邊加權有向圖，設計一個E*log(V)算法來找到一個邊緣，其去除導致的最大增幅（ 。可能是無限的）在從s到t的最短路徑的長度假設所有的邊權是嚴格爲正（提示：計算最短路徑的距離d(v)形式s到v並考慮降低成本c′(v,w)=c(v,w)+d(v)−d(w) ≥ 0）」的最短路徑上最重要的邊緣
我在網上閱讀過三（3）個人在1989年提出了複雜度算法O(E + V*log(V))什麼需要先進的數據結構，我認爲它是在圖形上（而不是有向圖）。如果有三位高級計算機科學家來開發這種算法，那麼對於入門課程來說，這不是一個太大的問題嗎？但是，只需O(E*log(V))就可以了。
你能幫我解決嗎？我不明白問題中的提示。
這是一個令人困惑的問題，我同意。這是我的一些想法。
的通過更換具有降低成本的原始成本降低A* search算法Dijkstra算法時「降低成本」術語和定義被用於：
c′(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0
的h(v) - h(w)部分是一種啓發式的下降功能，在一致（單調）啓發式的情況下，其成本不應超過邊緣成本，因此降低的成本仍大於0（請參見幻燈片14和15 here）
它看起來像Sedgewick su當搜索G'中的新/替換最短路徑時，使用原始距離函數（d(v)）作爲一致的啓發式，該路徑與原始G相同，但沿着從s到t的原始最短路徑移除一條邊。就個人而言，我不明白它如何幫助解決O(ElogV)中最重要的優勢問題。
還有一個類似的問題：查找圖中所有向下和向上的關鍵邊。根據定義，減少向下臨界邊緣的成本會降低總體SP成本。增加向上關鍵邊緣的成本會增加總體SP成本。所有關鍵的邊緣都可以在O(ElogV)中找到，請參閱第8頁的here。但是這並沒有回答什麼是最關鍵的邊緣問題（導致移除時最大SP增加）。
正如您所指出的，Malik，Mittal和Gupta（1989）在 O(E + V*log(V))時間解決了最重要的優勢問題。我還沒有找到原始MMG紙，但this presentation解釋得很好。據我所知，它可以用優先級隊列解決，不需要特定的數據結構。
對不起，實際上沒有回答原來的問題（解決方案中使用降低成本的圖中最重要的邊緣），但仍希望上面的鏈接和想法可能對某人有用。我很樂意看到Sedgewick的解決方案。
下面是根據Sedgewick的提示在最短路徑上找到關鍵邊算法的草圖。
首先，降低了成本C'（V，W）= C（V，W）+ d（V）-d（w）的對應於從小號在最短路徑的長度的增加到W¯¯，只是W¯¯之前通過v去的時候。 （如果v在從小號到瓦特然後該增加是0的最短路徑）（實際上D（v）是最短路徑從s到V和C（V長度，w）的成本去從v到W）。
從小號到牛逼是（S，...，v，T）假設的最短路徑，而我們刪除最後一個邊緣（ v，T）。然後，在最短路徑的長度噸增加從小號等於最小的C'（U，T）的所有入邊（U，T），與Ù！= v。
假設Ú使得C'（U，T）爲最小（靜止Ù！= V）。然後，按照最短路徑從小號到ü落後，直到你達到一個頂點，說W¯¯，屬於最短路徑從小號到牛逼（沒有任何去除邊緣）。從小號到牛逼的最短路徑是一樣的東西（S，...，W，...，V，T）。
注意，如果您刪除之間的邊緣W¯¯和牛逼，你會得到℃的最高增長「（U，T） INT的最短路徑。事實上，在案件之間的邊緣W¯¯和牛逼缺少的一個，只要通過頂點ü從去W¯¯到牛逼。在另一方面，注意去掉最後邊緣（V，T）將導致正是這一點增加。
現在，只需迭代w用t完成了什麼。找到一個頂點x這樣c'（x，w）是最小值，並且x不在最短路徑上。按照從小號到X落後的最短路徑，直到到達屬於最短路徑從小號到W¯¯頂點。
一旦到達s那麼您就可以確定刪除哪個頂點以使最短路徑的長度最大增加。