Cheapest Path Not Selected

[mimillman]

When there are multiple paths of the same length but one is cheaper than the other, the algorithm does not return the cheapest path.

Why is this? I have tried modifying the cost function from the example, but that has not seemed to work.

Thanks.

[wylee]

Hi. If you can provide some sample data that demonstrates this issue, I'd be happy to look into it and see if I can figure out what's going on.

One possibility is that you have parallel edges in your graph, a multigraph, which Dijkstra doesn't support. E.g., if you have nodes U and V and edges E and F, if you add the edge E from U to V and then add the edge F also from U to V, E will be silently overwritten, which could cause incorrect path-finding results.

If you need a multigraph, NetworkX might be a better choice. I've thought about adding a multigraph type to Dijkstra, but that's a low priority for me right now.

[marioferpa]

Same thing happened to me, and yes, I have two nodes with same input and output but different costs and the most expensive one seems to be overwriting the other. I will look for another library then.