Печать кратчайшего пути ч / б заданных узлов с использованием модифицированного Флойд Уоршолла

Question

Печать кратчайшего пути ч / б заданных узлов с использованием модифицированного Флойд Уоршолла

Я прочитал подход, данный Википедия распечатать кратчайший путь ч / б двух заданных точек на графике, изменив алгоритм Флойда Варшалла. Я закодировал это, но это не дает ожидаемого результата:

Инициализируйте все элементы в minimumDistanceMatrix[i][j] соответствующие веса в графе и всех элементов в матрице shortestPathCalculatorMatrix [i][j] до -1.

Затем :

// Find shortest path using Floyd–Warshall algorithm

for ( unsigned int k = 0 ; k < getTotalNumberOfCities() ; ++ k)
for ( unsigned int i = 0 ; i < getTotalNumberOfCities() ; ++ i)
for ( unsigned int j = 0 ; j < getTotalNumberOfCities() ; ++ j)
if ( minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j] < minimumDistanceMatrix[i][j] )
{
minimumDistanceMatrix[i][j] = minimumDistanceMatrix[i][k] + minimumDistanceMatrix[k][j];
shortestPathCalculatorMatrix [i][j] =  k;
}

Затем :

void CitiesMap::findShortestPathListBetween(int source , int destination)
{
if( source == destination || source < 0 || destination < 0)
return;

if( INFINITY == getShortestPathBetween(source,destination) )
return ;

int intermediate = shortestPathCalculatorMatrix[source][destination];

if( -1 == intermediate )
{
pathCityList.push_back( destination );
return ;
}

else
{
findShortestPathListBetween( source, intermediate ) ;
pathCityList.push_back(intermediate);
findShortestPathListBetween( intermediate, destination ) ;

return ;
}
}

P.S: pathCityList является вектором, который предполагается пустым до вызова findShortestPathListBetween сделан. В конце этого вызова этот вектор содержит все промежуточные узлы.

Может кто-нибудь указать, где я могу пойти не так?

8

algorithm c++floyd-warshall shortest-path

Решение

Другие решения

Немного поздно, но вышеприведенный код имеет недостатки …. это не должно быть next[i][j]=next[k][j] но правильный код для нахождения это next[i][j]=next[i][k]

Попробуйте сами на примере ввода, и вы узнаете, почему это работает и почему предыдущий неверен

0

Источник

Accepted Answer

Статья в Википедии ужасна. Помимо неверного представления (на мой взгляд) канонической формы алгоритма Флойда – Варшалла, он представляет собой псевдокод с ошибками.

Намного проще (и более прямым) не итерировать по индексам, а по вершинам. Кроме того, каждый предшественник (обычно обозначается πне next), необходимо указать на ее, хорошо, предшественник, не текущая временная вершина.

Имея это в виду, мы можем исправить их сломанный псевдокод.

for each vertex v
dist[v][v] ← 0
for each edge (u,v)
dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for each vertex k
for each vertex i
for each vertex j
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
next[i][j] ← next[k][j]

Обратите внимание, что я изменил три вложенных цикла для итерации по вершинам, а не по индексам, и исправил последнюю строку для ссылки на предыдущий узел, а не на любой промежуточный узел.

Объяснение того, почему это правильно, и как работает матрица предшественника, можно найти на Algoritmy.net.

Вышесказанное требует некоторой инициализации. К счастью, это легко, поскольку мы уже знаем первого предшественника каждого узла: если есть прямой путь от i в j, затем i является jПредшественник Если нет прямого пути, значит, нет предшественника.

for each vertex i
for each vertex j
if w(u,v) = ∞ then
next[i][j] ← NIL
else
next[i][j] ← i

NIL это просто заполнитель для любого не вершинного значения. В объектно-ориентированном коде это обычно null ссылка / указатель. При реализации графа в качестве матрицы смежности это может быть любой индекс, не соответствующий вершине, например, -1 или | V | +1.

Они также обеспечивают исправленную траекторию реконструкции:

function path(P, i, j)
if i = j then
write i
else if next[i][j] = NIL then
write "no path exists"else
path(P, i, P[i][j])
write j

7