Shortest Path Doesn't Support Negative Edge Weights ProperlyΒ #145
Description
Hi,
First off, thank you so much for implementing this graph library, it's made some of my recent projects so much easier not having to implement all my own algorithms!
However I've found something that I'd be interested in the maintainer's views on. From looking at the code it appears as though the shortestPath
function is using a variant of Djikstra's algorithm to find the shortest path, now this is fine, but in my particular use case I was using negative edge weights (because I wanted to find the longest path through a DAG) and I was getting different answers each time I ran the code. Eventually after some searching I realised that Djikstra's doesn't support negative edge weights: https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm, but this wasn't clear from the function documentation. Now I realise my use case is slightly novel but I wondered if it would be possible to at least add a health warning/error case to the function so that people don't fall down the same hole that I did?
In the end I implemented shortest path via repeated DFS and TopologicalSorting so this isn't a huge blocker for me, but I wanted to add to the library in any way I could and thought this would be a good start.
Again huge thanks for this library