anthony - 6 months ago 43

Java 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. I**mplementation 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.

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

Source (Stackoverflow)