我只是想確保這會工作。你能找到使用Dijkstra算法的最佳路徑嗎？你是否必須首先將距離初始化爲-1，然後更改鬆弛子程序以檢查它是否更大？Dijkstra的算法找到最權重的路徑
這是針對沒有任何負面權重的問題。
這實際上是該問題：
假設給出一個電話網，它是一個曲線圖 ģ其頂點代表交換機中心和其邊緣代表通信的兩個中心之間 線的圖。邊緣由其帶寬最低的帶寬邊緣標記。給出一個算法，給定一個圖和兩個開關中心 和b，將輸出a和b之間路徑的最大帶寬。
這項工作？
編輯：
我發現這一點：
提示：基本子程序將是非常相似的子程序的Dijkstra放鬆。 假設我們有一個邊（u，v）。如果min {d [u]，w（u，v）}> d [v]那麼我們應該更新 d [v] min {d [u]，w（u，v）}（因爲到你再到v的帶寬爲 min {d [u]，w（u，v）}，這比我們目前的還要多）。
不完全確定這是什麼意思，但因爲所有距離在初始化時都是無窮大。所以，我不知道這是如何工作的。任何線索？
我不確定Djikstra的路要走。負重對吉克斯特拉來說是壞事，壞事。
我想，你可以通過邊的權重排序，並開始刪除最低重量邊緣（最壞的瓶頸），並查看是否圖形仍處於連接狀態（或者至少你的起點和終點）。圖表被破壞的時刻是當你知道你消除了瓶頸時，你可以看看這個邊緣的值來獲得帶寬。 （如果我沒有弄錯，每次迭代需要O（E）時間，並且您需要O（E）迭代來找到瓶頸邊緣，所以這是O算法。 ：你必須認識到最大的路徑並不一定是最高的帶寬：你想要最大化min({edges in path})的值，而不是sum({edges in path})
@bdares他說沒有負權 – 2011-04-18 04:03:48
如果原始圖沒有負權重，則否定它們會使它們爲負數......這是您使用最短路徑算法尋找最長路徑時首先考慮的事項。 – bdares 2011-04-18 04:06:50
@bdares你可以重寫算法來計算最長的路徑... – 2011-04-18 04:08:30
計算流量可能更適用，但流量允許使用多個路徑。
只反轉邊緣權重，也就是說，如果邊緣權重是d考慮它，而不是爲d^-1。然後做Dijkstra的正常進行。初始化所有距離到無限遠爲正常。
您可以使用Dijkstra算法來找到一個最長的路徑，但小號因爲你只有兩個交換中心，我不明白你爲什麼需要像Dijkstra那樣訪問每個節點。最喜歡的是一個更優化的方法，比如分支和界限算法。
通過修改Dijkstra's來計算所有其他頂點的最大帶寬，您可以輕鬆解決這個問題。
您不需要將起始頂點初始化爲-1。
Algorithm: Maximum Bandwidth(G,a)
Input: A simple undirected weighted graph G with non -ve edge weights, and a distinguished vertex a of G
Output: A label D[u], for each vertex u of G, such that D[u] is the maximum bandwidth available from a to u.
Initialize empty queue Q;
Start = a;
for each vertex u of G do,
D[u] = 0;
for all vertices z adjacent to Start do{ ---- 1
If D[Start] => D[z] && w(start, z) > D[z] {
Q.enqueue(z);
D[z] = min(D[start], D[z]);
}
}
If Q!=null {
Start = Q.dequeue;
Jump to 1
}
else
finish();
這可能不是計算帶寬的最有效方式，但它現在可以想象得到。
你可以調整算法AllPairsShortestPaths（Floyd-Warshall）的一些邏輯嗎？ http://www.algorithmist.com/index.php/Floyd-Warshall%27s_Algorithm
將未連接的邊初始化爲負的無窮大，而不是採用最小的距離取最大值？
簡短的回答是：不，它不會工作。最長的路徑問題沒有Djikstra所假設的最佳子結構，所以Djikstra's不會給你正確的答案。 – bdares 2011-04-18 04:20:31