Warshall Floyd(全点対間最短路) (graph/shortest-path/warshall-floyd.hpp)

View this file on GitHub
Last update: 2026-08-10 06:54:42+00:00
Include: #include "graph/shortest-path/warshall-floyd.hpp"

Verified with

test/verify/aoj-grl-1-c.test.cpp

Code

#pragma once

#include <algorithm>
#include <cstddef>

/**
 * @brief Warshall Floyd(全点対間最短路)
 */
template <typename Matrix, typename T>
void warshall_floyd(Matrix& g, T INF) {
  for (std::size_t k = 0; k < g.size(); k++) {
    for (std::size_t i = 0; i < g.size(); i++) {
      for (std::size_t j = 0; j < g.size(); j++) {
        if (g[i][k] == INF || g[k][j] == INF) continue;
        g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}

#line 2 "graph/shortest-path/warshall-floyd.hpp"

#include <algorithm>
#include <cstddef>

/**
 * @brief Warshall Floyd(全点対間最短路)
 */
template <typename Matrix, typename T>
void warshall_floyd(Matrix& g, T INF) {
  for (std::size_t k = 0; k < g.size(); k++) {
    for (std::size_t i = 0; i < g.size(); i++) {
      for (std::size_t j = 0; j < g.size(); j++) {
        if (g[i][k] == INF || g[k][j] == INF) continue;
        g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}