Я реализовал Floyd-Warshall, чтобы вернуть расстояние между кратчайшим путем между каждой парой узлов/вершин и одиночный самый короткий путь между каждой из этих пар.
Есть ли способ заставить его возвращать каждый короткий путь, даже если для каждой пары узлов есть несколько путей, которые привязаны к кратчайшим? (Я просто хочу знать, трачу ли я время на пробуждение)
Если вам просто нужно подсчитать количество различных кратчайших путей, вы можете сохранить массив 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" - это инициализированное значение в массиве расстояний.
Функция "подсчета" в текущем одобренном ответе прерывается в некоторых случаях. Более полное решение было бы:
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.