Алгоритм Флойда: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
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); | |||
== Ссылки на задачи == | == Ссылки на задачи == | ||
* [http://acmp.ru/?main=task&id_task=135 ACMP #135 — Алгоритм Флойда] | * [http://acmp.ru/?main=task&id_task=135 ACMP #135 — Алгоритм Флойда] | ||
Версия от 20:09, 1 октября 2014
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-связность