Dijkstra算法多条边找到最小值

Question

我一直在尝试找到一种方法来获取图中顶点之间的最小距离和路径。我找到了一个解决方案，我可以根据自己的需要进行调整，而且它大部分都有效。我我说的实现： http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html#shortestpath_problem

只有一个问题，就是我要问的那个。如您所见，只有一条边 linking 两个顶点，如果是这样的话，我会得到我想要的结果。但是，在测试 class 中，如果我只添加另一条边 link 假设顶点 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);

在这种情况下（假设我试图从顶点 0 到 10 找到 path/distance）我仍然得到正确的路径（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

当它应该是 520 时它会给我错误的距离 (527) 因为我添加了从 vertex_0 到 vertex_2 的另一条边，重量更小所以它应该计算那个重量而不是前一个更大。

我不知道我是否表达清楚了，但如果您有任何想法，我将不胜感激。

注意：我没有把剩下的粘贴在这里，所以这不会变得很大但是检查 link，它都在那里

Answer 1

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

在这种情况下，它会在到达成本为 210 的 "Edge_12" 之前找到成本为 217 的 "Edge_1"。

对此的快速解决方法是首先找到连接两个节点的所有边中的最小值：

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

Dijkstra算法多条边找到最小值

Dijkstra Algorithm multiple edges find minimum

java

algorithm

graph

dijkstra