Флойд-Уоршалл: все кратчайшие пути

Если вам просто нужно подсчитать, сколько существует различных кратчайших путей, вы можете сохранить массив count в дополнение к массиву shortestPath. Вот быстрая модификация псевдокода из 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

Если вам нужен способ найти все пути, вы можете сохранить vector/arraylist-подобную структуру для каждой пары, которая будет разворачиваться и сворачиваться. Вот модификация псевдокода из той же 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)

Примечание: если k==j или k==i, это означает, что вы проверяете либо path[i][i]+path[i][j], либо path[i][j]+path[j][j], оба должны быть равны path[i][j], и это не помещается в next[i][j].

Реконструкция пути должна быть изменена для обработки vector. Подсчетом в этом случае будет размер каждого vector. Вот модификация псевдокода (python) из той же 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

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

Функция «подсчета» в текущем утвержденном ответе в некоторых случаях дает сбой. Более полное решение было бы:

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]

Причина этого в том, что для любых трех вершин i, j и k может существовать несколько кратчайших путей, идущих от i через k к j. Например, на графике:

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

Где есть два пути от i до j через k. count[i][k] * count[k][j] находит количество путей от i до k и количество путей от k до j, и умножает их, чтобы найти количество путей i -> k -> j.