В алгоритме Флойда-Уоршалла стоимость кратчайшего пути вычисляется для любой пары вершин. Дополнительная бухгалтерия позволяет нам вести фактический путь (список вершин) на кратчайшем пути.
Как я могу расширить Флойда-Уоршалла так, чтобы для любой пары вершин находились K кратчайших топ-K кратчайших путей? Например, для K = 3 результатом будет то, что 3 кратчайших пути вычисляются и поддерживаются?
Я использовал реализацию Java от Sedgewick.
Похоже, что Дейкстру было бы проще изменить для возврата N кратчайших путей. Поиску разрешается входить в вершину до тех пор, пока в вершину не войдут K кратчайших альтернатив.
Дополнительную информацию можно найти в статье в Википедии
Вы можете вызывать цикл несколько раз, используя дополнительное условие, которое может понравиться
for (int i = 0; i < V; i++) {
// compute shortest paths using only 0, 1, ..., i as intermediate vertices
for (int v = 0; v < V; v++) {
if (edgeTo[v][i] == null) continue; // optimization
for (int w = 0; w < V; w++) {
if (distTo[v][w] > distTo[v][i] + distTo[i][w] && distTo[v][i]+distTo[i][w]>min[k]) { //min[k] is the minimum distance calculated in kth iteration of minimum distance calculation
distTo[v][w] = distTo[v][i] + distTo[i][w];
edgeTo[v][w] = edgeTo[i][w];
}
}
// check for negative cycle
if (distTo[v][v] < 0.0) {
hasNegativeCycle = true;
return;
}
}
} Этот код вычислит K минимальных расстояний, которые различаются. Надеюсь, это поможет тебе.
Kразные пути одинаковой минимальной длины илиKпути разной длины, но короче любого другого пути? - person Codor schedule 23.08.2014