◉ Warshall-Floyd 法
Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://noshi91.github.io/algorithm-encyclopedia) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /algorithm-encyclopedia/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$ 最短経路を求めるということである。

詳細

(省略)

関連項目

Dijkstra 法
- Dijkstra 法は単一始点最短経路問題を解くアルゴリズムのひとつである。競技プログラミングでは Warshall-Floyd 法と並んで頻繁に利用される。
Bellman-Ford 法
- Bellman-Ford 法は単一始点最短経路問題を解くアルゴリズムのひとつである。Bellman-Ford 法は緩和を収束するまで繰り返すことで動作するが、これは Warshall-Floyd 法も同様である。

changelog

2021年02月12日「記事作成」 authors: kimiyuki, reviewers: kuretchi

license

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.