Floyd-Warshall: all shortest paths

Question

I've implemented Floyd-Warshall to return the distance of the shortest path between every pair of nodes/vertices and a single shortest path between each of these pairs.

Is there any way to get it to return every shortest path, even when there are multiple paths that are tied for shortest, for every pair of nodes? (I just want to know if I'm wasting my time trying)

Tonnage

save all the "shortest-paths" in a HashMap with key=path-length and value={set of shortest paths at this length}. Save the shotest-path length in a separate variable and after your algorithm is done, just pull the minimum value from the HashMap. – Jurisdiction

Answer 1

If you just need the count of how many different shortest path exist, you can keep a count array in addition to the shortestPath array. Here's is a quick modification of the pseudocode from wiki.

procedure FloydWarshall ()
    for k := 1 to n
        for i := 1 to n
            for j := 1 to n
                if path[i][j] == path[i][k]+path[k][j] and k != j and k != i
                    count[i][j] += 1;
                else if path[i][j] > path[i][k] + path[k][j]
                    path[i][j] = path[i][k] + path[k][j]
                    count[i][j] = 1

If you need a way to find all the paths, you can store a vector/arraylist like structure for each pair to expand and collapse. Here is a modification of the pseudocode from the same wiki.

procedure FloydWarshallWithPathReconstruction ()
    for k := 1 to n
        for i := 1 to n
            for j := 1 to n
                if path[i][k] + path[k][j] < path[i][j]
                    path[i][j] := path[i][k]+path[k][j];
                    next[i][j].clear()
                    next[i][j].push_back(k) // assuming its a c++ vector
                else if path[i][k] + path[k][j] == path[i][j] and path[i][j] != MAX_VALUE and k != j and k != i
                    next[i][j].push_back(k)

Note: if k==j or k==i, that means, you're checking either path[i][i]+path[i][j] or path[i][j]+path[j][j], both should be equal to path[i][j] and that does not get pushed into next[i][j].

Path reconstruction should be modified to handle the vector. The count in this case would be each vector's size. Here is a modification of the pseudocode (python) from the same wiki.

procedure GetPath(i, j):
    allPaths = empty 2d array
    if next[i][j] is not empty:
        for every k in next[i][j]:
            if k == -1: // add the path = [i, j]
                allPaths.add( array[ i, j] ) 
            else: // add the path = [i .. k .. j]
                paths_I_K = GetPath(i,k) // get all paths from i to k
                paths_K_J = GetPath(k,j) // get all paths from k to j
                for every path between i and k, i_k in paths_I_K:
                    for every path between k and j, k_j in paths_K_J:
                        i_k = i_k.popk() // remove the last element since that repeats in k_j
                        allPaths.add( array( i_k + j_k) )

    return allPaths

Note: path[i][j] is an adjacency list. While initializing path[i][j], you can also initialize next[i][j] by adding a -1 to the array. For instance an initialization of next[i][j] would be

for every edge (i,j) in graph:
   next[i][j].push_back(-1)

This takes care of an edge being the shortest path itself. You'll have to handle this special case in the path reconstruction, which is what i'm doing in GetPath.

Edit: "MAX_VALUE" is the initialized value in the array of distances.

Wingfooted

I managed to make it work by adding and k != j to the else if statement. I then wrote a recursive function to step through next. It interprets a value in next which is equal to the current node as meaning that the next node can be accessed directly. Is this a reasonable way of interpreting/unravelling the next matrix? Or is there a cleaner/clearer way of doing it? – Tonnage

@Tonnage Overlooked the k != j part. Edited my answer to reflect it. – Wingfooted

@Tonnage I added the code for path reconstruction. I've used -1 as the index if there is a direct edge; but your technique of storing one of the nodes is also fine. – Wingfooted

I notice you also added k != i, what is that for? Not sure I understand the -1 part. Where does an entry in next get set to -1? Is that what it is initialized to? Thanks again for the help – Tonnage

@Tonnage Added notes for more clarification. – Wingfooted

One more (hopefully last) question. The GetPath function returns 1,2,2,2,3,3,3,4 when I'd expect 1,2,3,4. Also when there are multiple routes through a node certain parts only get returned once. Should a pathSoFar variable be added and passed to the recursive function? Perhaps initialized to the initial i – Tonnage

Is something along the lines of the wrapper and inner function in question/answer 10543943 the way to go? The example giving me problems is a situation where going from 1->4 can be done by 1,2,3,4 1,2,4 or 1,3,4 – Tonnage

@Amadan Can your answer to 10543943 help here? – Tonnage

I guess my issue is how to handle all the branches from the multiple entries in next. Sorry for all the posts – Tonnage

@Tonnage You're right; this requires a better handling. I'll try something once I get back from work. – Wingfooted

I had a look at an intro to algorithms book and it suggested using a predecessor matrix where each entry p(i,j) is initialized to i unless i=j or path(i,j)=inf in which case p(i,j) = NIL then. At each iteration pi(i,j) = pi(k,j) if the path from i to j through k is shorter. This seems similar to the Bellman Ford solution here but I'm struggling to make it work. – Tonnage

@Tonnage Hopefully this new procedure (GetPath) helps you. Let me know if I've missed some obvious catch or optimization's. – Wingfooted

Thanks, that works. It does return some duplicate paths, but not sure if there is any cleaner way to deal with that then by taking only the unique paths before returning allPaths – Tonnage

One small thing, I think a check is needed somewhere to prevent infinite recursion due to cycling. For example a graph with distances between all nodes of zero would get stuck in getPaths. Perhaps an array of visited nodes? – Tonnage

@Tonnage A cycle shouldn't occur in a shortest path. Do you have negative cycles? If you do then there is no correct shortest path for the graph. – Wingfooted

No negative cycles, but tried an example with zero cost cycles and that is where I got the infinite recursion. Would it be possible to add an array indicating a node has been visited to avoid the infinite recursion in this situation? – Tonnage

let us continue this discussion in chat – Wingfooted

Answer 2

The 'counting' function in the current approved answer flails in some cases. A more complete solution would be:

procedure FloydWarshallWithCount ()
for k := 1 to n
    for i := 1 to n
        for j := 1 to n
            if path[i][j] == path[i][k]+path[k][j]
                count[i][j] += count[i][k] * count[k][j]
            else if path[i][j] > path[i][k] + path[k][j]
                path[i][j] = path[i][k] + path[k][j]
                count[i][j] = count[i][k] * count[k][j]

The reason for this is that for any three vertices i, j, and k, there may be multiple shortest paths that run from i through k to j. For instance in the graph:

       3             1
(i) -------> (k) ---------> (j)
 |            ^
 |            |
 | 1          | 1
 |     1      |
(a) -------> (b)

Where there are two paths from i to j through k. count[i][k] * count[k][j] finds the number of paths from i to k, and the number of paths from k to j, and multiplies them to find the number of paths i -> k -> j.

Deposal

Answer 3

Supplements for the most voted answer:

1. in GetPath function, the command

i_k = i_k.popk() // remove the last element since that repeats in k_j

should be moved one line forward, in other words, into the loop of paths_I_K.

2. at the end of GetPath, duplicated paths should be removed.

The corresponding Python code is below and its correctness has been checked:

def get_all_shortest_paths_from_router(i, j, router_list, it=0):                                                                                                    
    all_paths = []
    if len(router_list[i][j]) != 0:
        for k in router_list[i][j]:
            if k == -1: # add the path = [i, j]
                all_paths.append([i, j])
            else: # add the path = [i .. k .. j]
                paths_I_K = get_all_shortest_paths_from_router(i,k,router_list,it+1) # get all paths from i to k
                paths_K_J = get_all_shortest_paths_from_router(k,j,router_list,it+1) # get all paths from k to j
                for p_ik in paths_I_K:
                    if len(p_ik) != 0:
                        p_ik.pop() # remove the last element since that repeats in k_j
                    for p_kj in paths_K_J:
                        all_paths.append(p_ik + p_kj)

    if it==0:
        all_paths.sort()
        all_paths = [all_paths[i] for i in range(len(all_paths)) if i == 0 or all_paths[i] != all_paths[i-1]]
    return all_paths

Bradford

Answer 4

There is a simpler way to do this. This version uses strings as nodes because that's what I needed but it is trivial to change to integers. schemaMatrix is just the path costs matrix calculated by FW.

NOTE: because of my unique needs this also generates a few paths that are longer than the shortest one (but unique). If you don't need those you can simply remove them (their length > shortest length) at the end.

Language is javascript.

function getSchemaPaths(schemaMatrix, start, end) {
  let deepCopy = function (el) {
    // careful with JS arrays
    return JSON.parse(JSON.stringify(el));
  };

  let visited = [];
  let paths = [];

  let getSchemaPathsHelper = function (
    schemaMatrix,
    start,
    end,
    currentNode,
    currentPath,
    paths,
    visited
  ) {
    // TODO: We should first ensure there is a path between start and end.

    let children = Object.keys(schemaMatrix[currentNode]);
    let filteredChildren = children.filter((c) => !visited.includes(c));

    // We have a full path
    if (currentNode === end) {
      paths.push(deepCopy(currentPath));
      return;
    }

    if (!visited.includes(currentNode)) {
      visited.push(currentNode);
    }

    visited = visited.concat(filteredChildren);
    console.log(currentPath);
    for (let j = 0; j < filteredChildren.length; j++) {
      let child = filteredChildren[j];

      getSchemaPathsHelper(
        schemaMatrix,
        start,
        end,
        child,
        currentPath.concat([child]),
        paths,
        deepCopy(visited)
      );
    }
  };

  getSchemaPathsHelper(
    schemaMatrix,
    start,
    end,
    start,
    [start],
    paths,
    visited
  );

  return deepCopy(paths);
}

Taiga