◉ Shortest Path Faster Algorithm

Kyopro Encyclopedia of Algorithms

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

詳細

(省略)

その他

• 基本的に常に Bellman-Ford 法より速いようである¹。

関連項目

• Bellman-Ford 法
  • Bellman-Ford 法をキューを用いて高速化したものが SPFA である。
• Dijkstra 法
  • Dijkstra 法を優先度付きキューでなく普通のキューを使うように修正するとほとんど SPFA になる。

外部リンク

• SPFAの紹介 - hogloidのブログ^archive.org
  • hogloid によるブログ記事。簡単な解説と実装例がある。

注釈

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

---

View full history / Report issues / Edit this page

changelog

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

license

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