在Graph中找到一個節點，使其他兩個節點之間的距離最小化

我有一個有向加權圖G，帶有V個頂點和E個邊。給定圖中的兩個節點，讓我們說A和B，並給定AB的權重表示爲w（A，B），我需要找到一個節點C，使得max（w（A，C），w （B，C））在所有可能性中都是最小的。通過可能性我的意思是所有的值C可以採取。我不知道它是否完全清楚，如果不是，我會盡量做得更精確。在Graph中找到一個節點，使其他兩個節點之間的距離最小化

來源

2012-11-13 Andrés

好的老路徑？ – Reactormonk

我一開始以爲。但由於我可能有多達10000個節點，我認爲不適合。 –

如果W（A，C）你真的是一個邊緣的只是重量，然後檢查直接連接到A依次所有節點，總成本在最壞的大小該圖表與您所期望的一樣好，假設您始終需要閱讀圖表。大多數路徑尋找算法（如http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）實際上是計算從A到每個成本最小的路徑的代價，如果用w（A，C）表示從A到C的最小代價路徑的代價，其他節點。如果您既有從A到達每個節點的成本，又有從每個節點到B的成本，則可以通過依次查看每個節點來解決您的問題。

所以，一個人運行來計算成本A到所有其他節點，然後反轉節點中的邊，並執行另一次運行以計算出從B到反轉圖中每個其他節點的最低成本路徑。然後，對於每個節點，您都有最低成本w（A，C）和最低成本w（C，B）的成本，因此您可以依次檢查每個節點以查看哪個節點最好。

如果你的圖形包含循環，那麼你需要像http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm這樣的東西。如果它有負循環，你將會遇到問題。

來源

2012-11-13 04:56:45 mcdowella

是的。我這件事完全符合我的需求。非常感謝你 –

我不認爲它的工作。請注意，Dijkstra正在尋找最短路徑，並且沒有保證您需要最短路徑。查看計數器示例：A-（15）-B-（15）-C和一個額外節點D，其中（w（A，D）= 1，w（D，C）= 20）。找到的最短路徑是'A-> D-> C'，而路徑'A-> B-> C'使部分距離最小化，並且有效地：'max {w（A，B），w（B，c ）} amit

你說得對。我會看看我能否以某種方式修改Dijkstra。感謝您的幫助 –

不是非常清楚你在問什麼，但是這裏有一種加權距離的方法：把它當作R^n中的距離問題來處理，其中任何維度中C的實際直線距離乘以該維度的權重的路徑來獲得加權距離。將整個表達式作爲加權距離的總和，並使用二階導數測試來最大化該表達式。

乾杯，安德魯

來源

2012-11-13 04:52:32

在Graph中找到一個節點，使其他兩個節點之間的距離最小化

回答

相關問題