Dijkstra算法多邊找到最小值

我一直在試圖找到一種方法來獲取圖中頂點之間的最小距離和路徑。我找到了適合我的必需品的解決方案，而且大部分都可以工作。我mplementation我在說：http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html#shortestpath_problem Dijkstra算法多邊找到最小值

只有一個問題，這是我問的一個。正如你所看到的，只有一條邊鏈接兩個頂點，如果是這種情況，我會得到我想要的結果。然而，在測試類，如果我只是添加另一個邊緣連接假設頂點1和Vertex 2比另一個像這樣的低重量：

addLane("Edge_0", 0, 1, 85); 
addLane("Edge_1", 0, 2, 217); 
addLane("Edge_12", 0, 2, 210); //as you can see, added this one 
addLane("Edge_2", 0, 4, 173); 
addLane("Edge_3", 2, 6, 186); 
addLane("Edge_4", 2, 7, 103); 
addLane("Edge_5", 3, 7, 183); 
addLane("Edge_6", 5, 8, 250); 
addLane("Edge_7", 8, 9, 84); 
addLane("Edge_8", 7, 9, 167); 
addLane("Edge_9", 4, 9, 502); 
addLane("Edge_10", 9, 10, 40); 
addLane("Edge_11", 1, 10, 600);

在這種情況下（可以說我嘗試找到從頂點0到10路/距離）我仍然得到正確的路徑（Vertex_0 - > Vertex_2 - > Vertex_7 - > Vertex_9 - > Vertex_10），但如果我只是做：

dijkstra.getShortestDistance(nodes.get(10)); //to get the distance from the source to the destination which in this case is the Vertex_10

它會給我錯了距離（527）當它應該是520時，因爲我從vertex_0到vertex_2增加了一個較低重量的邊，所以它應該計算該重量，而不是前一個大蒙古包。

我不知道我是否讓自己清楚，但如果您有任何想法，我很感激。

注：我沒有粘貼在這裏休息所以這不會得到巨大的，但檢查鏈接，這一切都沒有

來源

2016-11-29 anthony

這是非常簡單的：要麼使下面的執行Dijkstra算法的正確實施來找到[這裏]（https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode）或只是遍歷兩個節點之間的最短邊（最小權重） – Paul

你怎麼樣那些距離？這些方法是私人的... –

我之前說過，我適應了它，所以我做了我需要的公共 – anthony

因爲該方法getDistance的的。該方法假定節點，目標對由一條邊連接。

private int getDistance(Vertex node, Vertex target) { 
    for (Edge edge : edges) { 
     if (edge.getSource().equals(node) && edge.getDestination().equals(target)) { 
      return edge.getWeight(); 
     } 
    } 
    throw new RuntimeException("Should not happen"); 
}

在這種情況下，將達到「Edge_12」成本210

速戰速決這將是第一個發現的最小連接兩個所有邊緣之前找到「Edge_1」成本217節點：

private int getDistance(Vertex node, Vertex target) { 
    Integer weight = null; 
    for (Edge edge : edges) { 
     if (edge.getSource().equals(node) && edge.getDestination().equals(target)) { 
      if (weight == null || edge.getWeight() < weight) { 
       weight = edge.getWeight(); 
      } 
     } 
    } 
    if (weight == null) { 
     throw new RuntimeException("Should not happen"); 
    } 
    return weight; 
}

來源

2016-11-29 11:33:55 Junior

它實際上是如此基本該死。感謝人！感謝大家給我的快速幫助 – anthony

Dijkstra算法多邊找到最小值

回答

相關問題