Warshall-Floyd 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /warshall-floyd#noredirect を利用してください。
name
Warshall-Floyd 法
short description
Warshall-Floyd 法とは、全点対間最短経路問題を解くアルゴリズムのひとつ。負閉路が存在するなら検出できる。定数倍の軽い $O(\vert V \vert ^ 3)$ で動く。
input
辺重み $c : E \to \mathbb{R}$ 付き有向グラフ $G = (V, E)$
output
各頂点の組 $(s, t) \in V \times V$ に対し $s$-$t$ 最短路長
time complexity
$O(\vert V \vert ^ 3)$

概要

Warshall-Floyd 法とは、全点対間最短経路問題を解くアルゴリズムのひとつ。 負閉路が存在するなら検出できる。定数倍の軽い $O(\vert V \vert ^ 3)$ で動く。

全点対間最短経路問題を解くとは、辺に重みが付いた有向グラフ $G$ が与えられたとき、頂点の組 $(s, t)$ のすべてに対して $s$-$t$ 最短経路を求めるということである。

詳細

(省略)

関連項目