You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Describe the bug
The Dijkstra algorithm is not well implemented because when it selects the the next node to visit, it does by choosing the cheapest adjacent node (to the current node) instead of the non visited node with the cheapest path from the starting node. This means that it will not visit some nodes (because it acts kind of like a greedy algorithm) and it will produce incorrect shortest paths.
To Reproduce
Taking DijkstraTest1_Success and modifying by adding 2 nodes:
var w = graph.AddVertex('W');
var z = graph.AddVertex('Z');
Describe the bug
The Dijkstra algorithm is not well implemented because when it selects the the next node to visit, it does by choosing the cheapest adjacent node (to the current node) instead of the non visited node with the cheapest path from the starting node. This means that it will not visit some nodes (because it acts kind of like a greedy algorithm) and it will produce incorrect shortest paths.
To Reproduce
Taking DijkstraTest1_Success and modifying by adding 2 nodes:
var w = graph.AddVertex('W');
var z = graph.AddVertex('Z');
And adding 2 edges:
graph.AddEdge(a, w, 50);
graph.AddEdge(w, a, 50);
graph.AddEdge(w, z, 1);
graph.AddEdge(z, w, 1);
We get that the path from a to z is not found:
shortestPathList[5].Vertex.Should().Be(w);
shortestPathList[5].Distance.Should().Be(50);
shortestPathList[5].PreviousVertex.Should().Be(a);
shortestPathList[5].ToString().Should()
.Be($"Vertex: {w} - Distance: {50} - Previous: {a}");
shortestPathList[6].Vertex.Should().Be(z);
shortestPathList[6].Distance.Should().Be(51);
shortestPathList[6].PreviousVertex.Should().Be(w);
shortestPathList[6].ToString().Should()
.Be($"Vertex: {z} - Distance: {51} - Previous: {w}");
Expected shortestPathList[6].Distance to be 51.0, but found 1.7976931348623157E+308.
You can also make it find wrong paths if you cheat the greedy nature of the implementation.
Expected behavior
It should find a path from a to z.
Actual behavior
It doesnt.
The text was updated successfully, but these errors were encountered: