Изучите алгоритм Флойда—Уоршелла
Нам дан ориентированный или неориентированный взвешенный граф с вершинами. Нам нужно найти кратчайшее расстояние между каждой парой вершин и .
Граф может содержать рёбра с отрицательными весами, но он не должен содержать циклов отрицательного веса.
Этот алгоритм также можно использовать для обнаружения отрицательных циклов: если после завершения алгоритма мы получим
для некоторой вершины , то граф содержит отрицательный цикл.
Алгоритм Флойда—Уоршелла строит ответ шаг за шагом.
На каждом этапе мы решаем, полезно ли проходить через ещё одну вершину при переходе от к .
Перед этапом значение d[x][y] хранит длину кратчайшего пути от к , чьи внутренние вершины принадлежат только множеству
Здесь внутренние вершины означают все вершины на пути, кроме начала и конца.
Для начального этапа мы задаём:
d[x][y] = w[x][y], если есть ребро из в с весом ;d[x][y] = inf, если ребра нет;d[x][x] = 0 для каждой вершины .Теперь предположим, что мы находимся на этапе и хотим обновить матрицу.
Для каждой пары вершин есть две возможности:
Во втором случае путь можно разбить на две части:
Обе эти части используют только внутренние вершины из множества , поэтому их длины уже вычислены.
Следовательно, переход таков:
Так что на каждом этапе мы просто пытаемся улучшить каждую пару , проходя через вершину .
После всех этапов d[x][y] будет содержать длину кратчайшего пути от к $y, или inf`, если такого пути не существует.
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}