Алгоритм Флойда: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
| Строка 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);
Ссылки на задачи
- ACMP #135 — Алгоритм Флойда
- ACMP #136 — Алгоритм Флойда - 2
- ACMP #137 — Существование пути
- ACMP #562 — Слабая K-связность