Dijkstra confusion

 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:

1. Dijkstra just does not work correctly if there are negative weights.
2. 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. 
3. 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:

When we try to find the shortest path from n0 to n2, using [2], we can see:

dijkstra
shortest path length: 1.0
johnson
shortest path length: -8.0
bellman_ford
shortest path length: -8.0

<ipython-input-25-7a1de3894d98>:13: 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 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

1. Dijkstra, E.W. A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959).
2. https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.dijkstra.html
3. https://stackoverflow.com/questions/53532109/can-i-use-dijkstras-algorithm-on-dag-with-negative-weighted-edges
4. 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]))