Dijkstraアルゴリズム複数の辺が最小値を見つける

Question

グラフ内の頂点間の最小距離とパスを取得する方法を見つけようとしています。私は自分の必需品に適応したソリューションを見つけました。私施行私は話している：http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html#shortestpath_problem

私が約質問している一つの問題があります。あなたが見ることができるように、2つの頂点を結ぶ唯一の辺があります。その場合、私は必要な結果を得ます。 しかし、テストクラスで私はちょうどのは、このような他のものよりも低体重で頂点1と頂点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); 

この場合は、イム検索しようと言うことができます10の頂点0からのパス/距離）私はまだ正しいパス（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 

それは私に間違った距離を与えます私は頂点_0から頂点_2までの別の辺を低い重みで追加したので、520となるはずです（527）。ゲー

私は自分自身を明確にしたかどうか分かりませんが、もしあなたがアイデアを持っていれば、私はそれを感謝します。

注：私は、これは巨大な取得が、リンクをチェックしないと、ここで休息を貼り付けていなかった、それがための方法getDistanceのすべてが

Answer 1

です。この方法では、ノード、ターゲットペアがちょうど1つのエッジで接続されていることを前提としています。この場合

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"); 
} 

それはコスト217で「Edge_1を」見つける「Edge_12を」到達する前にコスト210

とこれにクイックフィックスは、最初の2つを接続するすべてのエッジの最小値を見つけることであろうノード：これはかなり簡単です

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; 
}