search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.82k stars 96 forks source link

Shortest Path Doesn't Support Negative Edge Weights Properly #145

Open jonathanrainer opened 1 year ago

jonathanrainer commented 1 year ago

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

dominikbraun commented 1 year ago

Hi,

I'm happy to hear you like this library! You're right – Dijkstra's algorithm doesn't support negative edge weights, and this should indeed be documented to avoid confusion. For very generic functions such as ShortestPath, this library usually prefers the more general, less performant solution over a less general, more performant solution, so it really would make sense to support negative edge weights even if the algorithm would be slightly slower. There would still be place for faster solutions tailored to a specific use case.

So I'm open to replace the implementation of ShortestPath with an algorithm that can deal with negative edge weights, such as Bellman-Ford or Johnson's algorithm, which modifies Dijkstra's algorithm to use Bellman-Ford. But I will admit that I'm not deep into these algorithms and can't make an informed decision yet, so any suggestions are welcome.

jonathanrainer commented 1 year ago

Hi,

I'm happy to hear you like this library! You're right – Dijkstra's algorithm doesn't support negative edge weights, and this should indeed be documented to avoid confusion. For very generic functions such as ShortestPath, this library usually prefers the more general, less performant solution over a less general, more performant solution, so it really would make sense to support negative edge weights even if the algorithm would be slightly slower. There would still be place for faster solutions tailored to a specific use case.

So I'm open to replace the implementation of ShortestPath with an algorithm that can deal with negative edge weights, such as Bellman-Ford or Johnson's algorithm, which modifies Dijkstra's algorithm to use Bellman-Ford. But I will admit that I'm not deep into these algorithms and can't make an informed decision yet, so any suggestions are welcome.

My recollection is that Johnson's algorithm is more performant so if that's the choice I'd probably say go with that. However I also wonder if there's a case for including a version based on DFS and TopologicalSorting just for DAGs? As this is one of the fastest solutions I've found, and in fact was what I ended up using. But 100% yes a health warning would be great, even if it only saves one other person falling down a StackOverflow rabbit hole!

dominikbraun commented 1 year ago

However I also wonder if there's a case for including a version based on DFS and TopologicalSorting just for DAGs?

If that's the more performant choice for DAGs, then absolutely. This wouldn't even need to be in a dedicated function, a quick if g.Traits().IsDirected (followed by a in-algorithm cycle check, or a g.Traits().IsAcyclic) branch to run that algorithm would suffice.

dominikbraun commented 1 year ago

By the way, do you think it would be an option to directly return an error on negative weights and document that negative weights aren't supported, at least for the time being? This usually is the library's approach of handling invalid input.

jonathanrainer commented 1 year ago

Both of those sound great to me :)

jhsinger-klotho commented 1 year ago

Hi,

We have also needed this functionality, so i put up a pr https://github.com/dominikbraun/graph/pull/155. When taking in a single source and destination like the ShortestPath signature does, BellmanFord should be more performant, so i decided to implement it going that route.