Floyd-Warshall Algorithm (ワーシャルフロイド法)
(lib/graph/warshall_floyd.hpp)

• View this file on GitHub
• Last update: 2025-01-09 22:05:35+09:00
• Include: #include "lib/graph/warshall_floyd.hpp"

Floyd-Warshall Algorithm (ワーシャルフロイド法)

概要

全頂点間の最短経路問題を解くことができるアルゴリズムです。

使い方

• warshall_floyd(d, INF): 隣接行列 $d$ における、全頂点間の最短距離を求めます。(INF は到達不可能な距離とする。)

計算量

頂点数を $V$ とすると、$\mathrm{O}(V^3)$

Verified with

• test/aoj/grl/grl_1_c.test.cpp

Code

#pragma once

/**
 * @brief Floyd-Warshall Algorithm (ワーシャルフロイド法)
 * @docs docs/graph/warshall_floyd.md
 */

template <typename T>
void warshall_floyd(vector<vector<T>> &d, const T &INF) {
    int n = d.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(d[j][i] == INF || d[i][k] == INF) continue;
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
}

template <typename T>
void warshall_floyd_add(vector<vector<T>> &d, int u, int v, T cost) {
    int n = d.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            d[i][j] = min(d[i][j], d[i][u] + cost + d[v][j]);
        }
    }
}

#line 2 "lib/graph/warshall_floyd.hpp"

/**
 * @brief Floyd-Warshall Algorithm (ワーシャルフロイド法)
 * @docs docs/graph/warshall_floyd.md
 */

template <typename T>
void warshall_floyd(vector<vector<T>> &d, const T &INF) {
    int n = d.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(d[j][i] == INF || d[i][k] == INF) continue;
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
            }
        }
    }
}

template <typename T>
void warshall_floyd_add(vector<vector<T>> &d, int u, int v, T cost) {
    int n = d.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            d[i][j] = min(d[i][j], d[i][u] + cost + d[v][j]);
        }
    }
}

Back to top page