Алгоритм Флойда: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
== TLDR ==
<youtube width="300" height="180">c7ahlIwBL7o</youtube>
<youtube width="300" height="180">8JQ565Rz7d8</youtube>
<youtube width="300" height="180">LVnPNWwd-yo</youtube>
<youtube width="300" height="180">4njNaLG5p1A</youtube>
== Код ==
Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.
Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.


Строка 27: Строка 36:
             if (dist[a][v] == INF || dist[v][b] == INF)
             if (dist[a][v] == INF || dist[v][b] == INF)
                 continue;
                 continue;
             dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);
             dist[a][b] = min(dist[a][b], dist[a][v] + dist[v][b]);
             dist[a][b] = max(dist[a][b], -INF);
             dist[a][b] = max(dist[a][b], -INF);
         }
         }
Строка 40: Строка 49:
== Отрицательные циклы ==
== Отрицательные циклы ==


Вершина v лежит на отрицательном цикле, если после запуска Флойда dist[v][v] < 0.
Вершина v лежит на отрицательном цикле, если после запуска алгоритма Флойда dist[v][v] < 0. Наличие такой вершины — критерий отрицательного цикла в алгоритме Флойда.


При наличии отрицательных циклов между некоторыми парами вершин может не существовать кратчайшего пути. Между вершинами a и b нет кратчайшего пути, если существует вершина v, лежащая на отрицательном цикле, достижимая из a и из которой достижима b.
При наличии отрицательных циклов между некоторыми парами вершин может не существовать кратчайшего пути. Между вершинами a и b нет кратчайшего пути, если существует вершина v, лежащая на отрицательном цикле, которая достижима из a и из которой достижима b.


  const int NO_SHORTEST_PATH = -2e9;
  const int NO_SHORTEST_PATH = -2e9;
  for (int v = 0; v < vertexCount; v++)
  for (int v = 0; v < vertexCount; v++)
     for (int a = 0; a < vertexCount; a++)
     for (int a = 0; a < vertexCount; a++)

Текущая версия от 13:19, 21 апреля 2024

TLDR

Код

Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.

Идея алгоритма:

  • Инициализация. Пусть dist[a][b] — кратчайшее расстояние от a до b, но длиной не более чем одно ребро. Нетрудно понять, что dist — это просто матрица смежности графа (возможно, с небольшими модификациями):
  • Случай простого графа: dist[a][a] = 0, dist[a][b] = весу ребра (a, b); если ребра (a, b) нет, то dist[a][b] = INF;
  • Если есть кратные рёбра, то dist[a][b] = весу минимального ребра между a и b;
  • Если есть петли, то dist[a][a] = min(0, вес минимальной петли из a);
  • Шаг 0. Теперь разрешаем путям проходить через вершину 0. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][0] + dist[0][b]);
  • Шаг 1. Теперь разрешаем путям проходить через вершину 1. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][1] + dist[1][b]);
  • Повторяем до шага vertexCount - 1.
const int INF = 1e9;
vector<vector<int>> dist(vertexCount, vector<int>(vertexCount, INF));

for (int v = 0; v < vertexCount; v++)
    dist[v][v] = 0;

for (int i = 0; i < edgeCount; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    dist[a][b] = min(dist[a][b], w);
}

for (int v = 0; v < vertexCount; v++) {
    for (int a = 0; a < vertexCount; a++) {
        for (int b = 0; b < vertexCount; b++) {
            if (dist[a][v] == INF || dist[v][b] == INF)
                continue;
            dist[a][b] = min(dist[a][b], dist[a][v] + dist[v][b]);
            dist[a][b] = max(dist[a][b], -INF);
        }
    }
}

На что нужно обратить внимание:

  • При инициализации матрицы на главной диагонали должны быть нули (если нет петель отрицательного веса), а там, где рёбер нет — бесконечности;
  • При наличии отрицательных рёбер следует избегать присваиваний вида (INF - 1). Для этого, если хотя бы один из фрагментов пути равен INF, нужно делать continue;
  • При наличии отрицательных циклов расстояния могут очень быстро уменьшаться и приводить к отрицательным переполнениям. Поэтому нужно ограничивать отрицательные числа снизу.

Отрицательные циклы

Вершина v лежит на отрицательном цикле, если после запуска алгоритма Флойда dist[v][v] < 0. Наличие такой вершины — критерий отрицательного цикла в алгоритме Флойда.

При наличии отрицательных циклов между некоторыми парами вершин может не существовать кратчайшего пути. Между вершинами a и b нет кратчайшего пути, если существует вершина v, лежащая на отрицательном цикле, которая достижима из a и из которой достижима b.

const int NO_SHORTEST_PATH = -2e9;

for (int v = 0; v < vertexCount; v++)
    for (int a = 0; a < vertexCount; a++)
        for (int b = 0; b < vertexCount; b++)
            if (dist[a][v] != INF && dist[v][v] < 0 && dist[v][b] != INF)
                dist[a][b] = NO_SHORTEST_PATH;

Ссылки

Теория:

Демонстрация:

Код:

Задачи: