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

Ответ 1

Если вам просто нужно подсчитать количество различных кратчайших путей, вы можете сохранить массив 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

Примечание: path[i][j] - список смежности. При инициализации path[i][j] вы также можете инициализировать next[i][j], добавив в массив -1. Например, инициализация next[i][j] будет

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

Это заботится о том, чтобы край был самым коротким путем. Вам придется обрабатывать этот специальный случай в восстановлении пути, что я и делаю в GetPath.

Изменить: "MAX_VALUE" - это инициализированное значение в массиве расстояний.

Ответ 2

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

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 могут быть несколько кратчайших путей, которые исходят от я до k к j. Например, на графике:

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

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