如何找到兩個分離最廣的節點之間的距離

我正在通過前幾年的ACM編程競賽中試圖更好地解決圖形問題的問題。如何找到兩個分離最廣的節點之間的距離

我現在正在處理的一個是我給了任意數量的無向圖節點，它們的鄰居和連接節點的邊的距離。我需要的是距彼此最遠的兩個節點之間的距離（重量距離，而不是節點數量）。現在

，我有Dijkstra算法的形式：

// Dijkstra's Single-Source Algorithm 
private int cheapest(double[] distances, boolean[] visited) 
{ 
     int best = -1; 
     for (int i = 0; i < size(); i++) 
     { 
       if (!visited[i] && ((best < 0) || (distances[i] < distances[best]))) 
       { 
         best = i; 
       } 
     } 
     return best; 
} 

// Dijkstra's Continued 
public double[] distancesFrom(int source) 
{ 
     double[] result = new double[size()]; 
     java.util.Arrays.fill(result, Double.POSITIVE_INFINITY); 
     result[source] = 0; // zero distance from itself 
     boolean[] visited = new boolean[size()]; 
     for (int i = 0; i < size(); i++) 
     { 
       int node = cheapest(result, visited); 
       visited[node] = true; 
       for (int j = 0; j < size(); j++) 
       { 
         result[j] = Math.min(result[j], result[node] + getCost(node, j)); 
       } 

     } 
     return result; 
}

有了這個實現，我可以給它一個特定節點，它會給我從該節點的所有距離的列表。所以，我可以在距離列表中獲得最大距離，但我無法確定任何特定節點是兩端最遠的兩個節點之一。

所以我能想到的唯一解決方案就是在每個節點上運行這個Dijkstra算法，遍歷每個返回的距離列表並查找最大距離。在耗盡每個節點返回它的距離列表後，我應該得到任意兩個節點之間最大距離的值（兩個最廣泛分離的村莊之間的「道路」距離）。有一個更簡單的方法來做到這一點，因爲這似乎真的在計算上很昂貴。問題說可能有500個節點的樣本輸入，所以我不希望它花費過長的時間。這是我該怎麼做的嗎？

這裏是針對該問題的樣本輸入：

總節：5

邊緣：
節點2 - 連接 - 節點4距離/重量25個
節點2 - 連接 - 節點5 。距離/重量26個
節點3 - 連接 - 節點4距離/重量16個
節點1 - 連接 - 節點4距離/重量14

這個問題的答案樣本輸入是「67英里」。這是兩個最爲分散的村莊之間的公路長度。

所以我應該如何描述或者是否有一個更簡單，更少計算成本的方式？

來源

2008-10-04 mmcdole

您正在尋找的術語是「直徑」 – wnoise 2008-10-04 06:54:02

閱讀後：http：//mathworld.wolfram.com/GraphDiameter.html它們將直徑描述爲「直徑是必須遍歷的頂點數量最多從一個頂點到另一個頂點的路徑，當回溯，繞道或迴路的路徑被排除在考慮範圍之外。「 – mmcdole 2008-10-04 19:15:54

看起來你可以使用任：

雖然我不能給你很多指導 - 我不是專家。

來源

2008-10-04 06:05:53

您可以使用Dijkstra的執行如下命令：

隨機選擇一個節點，（一），從節點運行Dijkstra算法，並從中找到最遠的節點。將該節點標記爲節點b。
再次從節點b開始運行Dijkstra，並從中找到最遠的節點。將該節點標記爲節點c。

我沒有這方面的證據，但我認爲b和c將是最遠的節點。您可能需要再運行一次迭代（我仍在考慮它）。

來源

2008-10-04 06:03:32 DanJ

我想你可以想出一個微不足道的反例 – 2008-10-04 06:09:15

此外，很容易看出a會和c一樣c – 2008-10-04 06:10:45

It當圖被引導時，可能不是a與c相同的情況。 – 2008-10-04 06:11:53

所以有一個運行O（VlogV + E）的Dijkstra的實現給你的方法大致V^2logV + VE的複雜性。見DADS。但也許更直觀的是運行像Floyd-Warshall或Johnsons這樣的所有算法中的一個。不幸的是，對於密集圖（接近E = V^2的完整圖），它們都大致爲O（V^3）。

來源

2008-10-04 06:10:03 Purfideas

將邊權重乘以-1，找到新圖上的最短路徑。這將是對原始圖的最長路徑

來源

2008-10-04 06:14:15 Midhat

如果你希望那是

燮I，J {INF最長的最短路徑I，J {N：N = i和j之間的路徑的長度} }

你應該考慮像其他人提到的所有節點最短路徑算法，如Flyod-Warshall。這將按照O（V^3）的順序。

如果你想盡可能長的路徑是

燮I，J {N：N = i和j之間的路徑長度}

，你可以嘗試使用Midhat的想法。（這真的和原來的問題一樣複雜，正如評論中指出的那樣）我建議用1/w反轉權重，以保留正的權重，因爲原始權重是嚴格肯定的。

你可能要與負權交易時被貝爾曼和福特

來源

2008-10-04 08:30:34 Mastermind

的算法，這是該Roads in the North問題查找另一種算法？

來源

2008-10-04 08:33:00 Joseph

如何找到兩個分離最廣的節點之間的距離

回答

相關問題