Dijkstra is a famous algorithm for the shortest path problem. The original paper is from 1959 [1]:

(The format of this paper is interesting: almost no mathematical notation). Dijkstra's algorithm is not suited for all shortest path problems. Negative weights or lengths can cause problems. There are basically three different reasons I see mentioned:

- Dijkstra just does not work correctly if there are negative weights.
- Dijkstra does not work if there are negative cycles in the graph. This would imply that a problem with negative weights would work as long as there are no negative cycles.
- Keep things vague and mumble a bit about negative weights and negative cycles.

I notice that option 3 seems very popular. As a result, looking at questions about this on stackexchange, I see there is much confusion about this. Also, I see vague, misleading messages in documentation and error/warning messages. For instance, let's have a look at [2]:

Also, this routine does not work for graphs with negative distances. Negative distances can lead to infinite cycles that must be handled by specialized algorithms such as Bellman-Ford’s algorithm or Johnson’s algorithm.

Well, this is indeed sufficiently vague. We deal with option 3: we don't know if this is referring to reason 1 or 2. The same function that this documentation is about can produce the following warning:

UserWarning: Graph has negative weights: dijkstra will give inaccurate results if the graph contains negative cycles. Consider johnson or bellman_ford. distmat,pred = scipy.sparse.csgraph.dijkstra(spmat,indices=source,return_predecessors=True)

This seems to say we only need to worry about graphs with negative cycles. So that would be option 2.

#### A small counter example

In [3] a small acyclic graph (a DAG: Directed Acyclic Graph) is presented:

This example disproves that we just have to watch out for negative cycles. That means the documentation and warning messages should state clearly that the function scipy.sparse.csgraph.dijkstra does **not **work correctly with negative weights, irrespective of whether there are negative cycles.

#### Dijkstra variants

To make things more complicated: there are implementations of Dijkstra's algorithm that actually work with negative weights (they still require the absence of negative cycles) [4]. That means implementations need to state more precisely what the rules are and what input is allowed for the results to be accurate.

#### Conclusion

The implementation of Dijkstra's algorithm in [2] does not work with negative weights or lengths. Forget about negative cycles: that is not a useful check. It would be better if the documentation and the warning messages do not imply that we need to look at negative cycles.

#### References

- Dijkstra, E.W. A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959).
- https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.dijkstra.html
- https://stackoverflow.com/questions/53532109/can-i-use-dijkstras-algorithm-on-dag-with-negative-weighted-edges
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th Edition, https://algs4.cs.princeton.edu/44sp/ See the question: Does Dijkstra's algorithm work with negative weights?

#### Appendix: Python code

import scipy.sparse numnodes, numarcs = 3, 3 source, sink = 0, 2 rows = [0, 0, 1] cols = [1, 2, 2] values = [2, 1, -10] spmat = scipy.sparse.csr_matrix((values,(rows,cols)),shape=(numnodes,numnodes)) print("dijkstra") distmat,pred = scipy.sparse.csgraph.dijkstra(spmat,indices=source,return_predecessors=True) print("shortest path length: {}".format(distmat[sink])) print("johnson") distmat,pred = scipy.sparse.csgraph.johnson(spmat,indices=source,return_predecessors=True) print("shortest path length: {}".format(distmat[sink])) print("bellman_ford") distmat,pred = scipy.sparse.csgraph.bellman_ford(spmat,indices=source,return_predecessors=True) print("shortest path length: {}".format(distmat[sink]))

## No comments:

## Post a Comment