anthony anthony - 10 days ago 7
Java Question

Dijkstra Algorithm multiple edges find minimum

i've been trying to find a way to get the minimum distance and path between vertexes in a Graph. I've found a solution in which i adapted to my necessities and it mostly works. Implementation i'm talking about: http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html#shortestpath_problem

There's only one problem which is the one i'm asking about. As you can see there's only one edge linking two vertexes, and if that's the case i get the results i want.
However, in the test class if i just add another edge linking let's say Vertex 1 and Vertex 2 with a lower weight than the other one like this:

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


In this case (lets say im trying to find the path/distance from Vertex 0 to 10) i still get the correct path (Vertex_0 -> Vertex_2 -> Vertex_7 -> Vertex_9 -> Vertex_10) but if i just do:

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


It will give me the wrong distance (527) when it should be 520 because i added another edge from vertex_0 to vertex_2 with a lower weight so it should count that weight and not the previous one which is bigger.

I don't know if i made myself clear but if you have any ideas, i appreciate it.

Note: i didn't paste the rest here so this wouldn't get huge but check the link, it's all there

Answer

Because of the method getDistance. This method assumes that the node, target pair is connected by exactly one edge.

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

In this case it will find "Edge_1" with cost 217 before reaching "Edge_12" with cost 210.

A quick fix to this would be to first find the minimum of all edges connecting the two nodes:

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