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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 20: Строка 20:
* [http://e-maxx.ru/algo/floyd_warshall_algorithm e-maxx.ru — Алгоритм Флойда-Уоршелла]
* [http://e-maxx.ru/algo/floyd_warshall_algorithm e-maxx.ru — Алгоритм Флойда-Уоршелла]
* [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://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.neocities.org/lections/floyd.html brestprog.neocities.org — Алгоритм Флойда-Уоршелла]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5]
* [http://github.com/indy256/codelibrary/blob/master/java/src/FloydWarshall.java CodeLibrary — Floyd–Warshall algorithm]
* [http://github.com/indy256/codelibrary/blob/master/java/src/FloydWarshall.java CodeLibrary — Floyd–Warshall algorithm]

Версия от 20:13, 27 января 2016

int g[V_CNT][V_CNT], dist[V_CNT][V_CNT], INF = 1 << 30;

for (int i = 0; i < V_CNT; i++)
   for (int j = 0; j < V_CNT; j++)
       dist[i][j] = (g[i][j] ? g[i][j] : INF);

for (int k = 0; k < V_CNT; k++)
    for (int i = 0; i < V_CNT; i++)
        for (int j = 0; j < V_CNT; j++)
            if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]);
                dist[i][j] = max(dist[i][k] + dist[k][j], -INF);

Ссылки на задачи

Ссылки