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)
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.
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.
Supplements for the most voted answer:
GetPath function, the commandi_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.
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
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);
}
