wylee
Cheapest Path Not Selected
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.
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.
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.
