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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылки на задачи == * [http://acmp.ru/?main=task&id_task=135 ACMP #135 — Алгоритм Флойда] * [http://acmp.ru/?main=task&id_tas…»)
 
 
(не показано 15 промежуточных версий этого же участника)
Строка 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>
 
== Код ==
 
Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.
 
Идея алгоритма:
* Инициализация. Пусть 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;
 
== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/floyd_warshall_algorithm e-maxx.ru — Алгоритм Флойда-Уоршелла]
* [https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html cp-algorithms.com — Floyd-Warshall Algorithm]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Флойда]
* [http://brestprog.by/topics/floyd/ brestprog.by — Алгоритм Флойда-Уоршелла]
* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]
* [http://brilliant.org/wiki/floyd-warshall-algorithm brilliant.org — Floyd-Warshall Algorithm]
* usaco.guide — [https://usaco.guide/gold/shortest-paths?lang=cpp#floyd-warshall Shortest Paths with Non-Negative Edge Weights: Floyd-Warshall], [https://usaco.guide/adv/sp-neg?lang=cpp#floyd-warshall Shortest Paths with Negative Edge Weights: Floyd-Warshall]
Демонстрация:
* [https://www.cs.usfca.edu/~galles/visualization/Floyd.html www.cs.usfca.edu — Floyd-Warshall All-Pairs Shortest Path]
Код:
* [https://github.com/indy256/codelibrary/blob/master/java/graphs/shortestpaths/FloydWarshall.java indy256/codelibrary/java/graphs/shortestpaths/FloydWarshall.java]
* [https://github.com/ADJA/algos/blob/master/Graphs/FloydWarshall.cpp ADJA/algos/Graphs/FloydWarshall.cpp]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/FloydWarshall.java kevin-wayne/algs4/FloydWarshall.java]
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; — часть 5]
* [http://acmp.ru/?main=task&id_task=135 ACMP #135 &mdash; Алгоритм Флойда]
* [http://acmp.ru/?main=task&id_task=135 ACMP #135 &mdash; Алгоритм Флойда]
* [http://acmp.ru/?main=task&id_task=136 ACMP #136 &mdash; Алгоритм Флойда - 2]
* [http://acmp.ru/?main=task&id_task=136 ACMP #136 &mdash; Алгоритм Флойда - 2]
* [http://acmp.ru/?main=task&id_task=137 ACMP #137 &mdash; Существование пути]
* [http://acmp.ru/?main=task&id_task=137 ACMP #137 &mdash; Существование пути]
* [http://acmp.ru/?main=task&id_task=562 ACMP #562 &mdash; Слабая K-связность]


[[Category:Кратчайшие пути между всеми парами вершин]]
[[Category:Кратчайшие пути между всеми парами вершин]]

Текущая версия от 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;

Ссылки

Теория:

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

Код:

Задачи: