Shortest Path Faster Algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /spfa#noredirect を利用してください。
name
Shortest Path Faster Algorithm
short description
Shortest Path Faster Algorithm (SPFA) とは、単一始点最短経路問題を解くアルゴリズムのひとつ。Bellman-Ford 法をキューを使って定数倍高速化したものであり、優先度付きキューでなく普通のキューを使う Dijkstra 法のようなものでもある。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。
input
辺重み $c : E \to \mathbb{R}$ 付き有向グラフ $G = (V, E)$ および頂点 $s \in V$
output
各頂点 $t \in V$ に対し $s$-$t$ 最短路長
time complexity
$O(\vert V \vert \cdot \vert E \vert)$

概要

Shortest Path Faster Algorithm (SPFA) とは、単一始点最短経路問題を解くアルゴリズムのひとつ。Bellman-Ford 法をキューを使って定数倍高速化したものであり、優先度付きキューでなく普通のキューを使う Dijkstra 法のようなものでもある。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。

詳細

(省略)

その他

関連項目

外部リンク

注釈

  1. 「少なくともベルマンフォードより遅くなったことはありません」 SPFAの紹介 - hogloidのブログarchive.org