Алгоритм Флойда

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-связность

Ссылки

• e-maxx.ru — Алгоритм Флойда-Уоршелла
• neerc.ifmo.ru/wiki — Алгоритм Флойда
• brestprog.neocities.org — Алгоритм Флойда-Уоршелла
• algorithmica.org — Кратчайшие пути в графе
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5
• CodeLibrary — Floyd–Warshall algorithm
• Algos — Floyd–Warshall algorithm