2
$\begingroup$

Mathematica uses Bellman-Ford to find a shortest path between two vertices when the edge lengths are negative:

g = SparseArray[{{1,2} -> -1,{1,3} -> -1,{2,4} -> -1,{3,4} -> -1}]  
GraphPath[g,1,4]

yields

{1,2,4}

I want to find all such shortest paths. In the example above, {1,3,4} is another shortest path.

Goal: I'm testing a non-Mathematica shortest path algorithm against Mathematica. My algorithm also lazily finds only one shortest path, but it's different from the path Mathematica finds. I need to confirm my algorithm's shortest path really is a shortest path.

I realize I could just compare the path lengths (if they're equal, my algorithm has found a shortest path), but that wouldn't catch other errors in the algorithm (eg, if it's inventing edges or nodes or something).

I also realize I could have Mathematica find all paths or something and filter for the shortest ones, but that seems inefficient for larger graphs.

I've read Finding all shortest paths between two vertices, but

  1. I couldn't get it to work with Mathematica 9, and, more importantly
  2. it appears to be for positive-length edges.

NOTE: I realize I'm using a SparseArray for a graph above, but Mathematica seems to be OK with this.

Improve this question
$\endgroup$
4
  • $\begingroup$ duplicate of mathematica.stackexchange.com/questions/4128/… ? $\endgroup$
    – Andreas Lauschke
    Sep 12, 2013 at 18:22
  • $\begingroup$ I mention that question in my question. I don't think it's a duplicate because my graph has negative edge lengths. $\endgroup$
    – user1722
    Sep 12, 2013 at 18:27
  • $\begingroup$ I noticed that, but you could turn the -1 into +1 and look for maximum flow paths. And to find ALL paths attaining a certain flow is an NP-hard problem. So when you say "... find all paths or something and filter for the shortest ones, but that seems inefficient for larger graphs ..." keep in mind that IN GENERAL this could be NP-hard, as in theory all paths could be maximal (minimal). You also don't further specify what your graphs in general will look like. The small example you gave has only -1 on all arcs and no circles. Will your "large" ones have that same property? $\endgroup$
    – Andreas Lauschke
    Sep 12, 2013 at 18:35
  • $\begingroup$ Because with circles and negative arc lengths you could get -infinity. $\endgroup$
    – Andreas Lauschke
    Sep 12, 2013 at 18:36

1 Answer 1

Reset to default
1
$\begingroup$

I think I have an idea. You could modify Dijkstra in the following manner. At the innermost point in the loop structure there is an update step where you compare the new distance with the shortest distance found so far. If it's shorter, then you do a few update steps (like setting the shortest-distance-so-far to be the new one found, relabeling nodes, etc.). However, when they are EQUAL (and that would have to be the case when you found a new valid minimal path), you could now record the new ones attaining the same length in a list. Unless I'm missing something, that should give you a list of all shortest paths, and this should work for negative arc lengths as well.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.