Dijkstra Algorithm multiple edges find minimum

Question

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

this is pretty trivial: either make a proper implementation of dijkstra that follows the implementation found here or just traverse the shortest edge (least weight) between two nodes — user4668606
– user4668606, Commented Nov 29, 2016 at 11:28
how are you getting those distances? those methods are private.... — ΦXocę 웃 Пepeúpa ツ
– ΦXocę 웃 Пepeúpa ツ, Commented Nov 29, 2016 at 11:40
i said before that i adapted it so i made the ones i needed public — anthony
– anthony, Commented Nov 29, 2016 at 11:53

Junior · Accepted Answer · 2016-11-29 11:42:10Z

2

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

edited Nov 29, 2016 at 11:42

answered Nov 29, 2016 at 11:33

Junior

1105 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

anthony Over a year ago

it was actually so basic damn. thanks though man! appreciate the quick help everyone gave me

Collectives™ on Stack Overflow

Dijkstra Algorithm multiple edges find minimum

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related