java - Dijkstra算法多条边找到最小值

Question

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

只有一个问题，就是我要问的那个。如您所见，只有一条边连接两个顶点，如果是这样的话，我会得到我想要的结果。但是，在测试类中，如果我只添加另一个边缘链接，让我们说顶点 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 的路径/距离)我仍然得到正确的路径(顶点_0 -> 顶点_2 -> 顶点_7 -> 顶点_9 -> 顶点_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 添加了另一条具有较低权重的边，所以它应该计算该权重而不是前一个更大的权重。

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

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

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