A-1アルゴリズム・プログラミング · アルゴリズム

最短経路探索

Shortest Path Search

さいたんけいろたんさく

重み付きグラフで、2つの頂点の間を結ぶ経路のうち、通る辺の重み（距離や費用）の合計が最小になる経路を求めること。負の重みが無ければダイクストラ法、負の重みがあればベルマンフォード法などを使い、カーナビの経路案内やネットワークの経路制御に応用される。

共有:

他の資格での定義

グラフ上の2点間で、辺の重みの合計が最小になる経路を求める処理。カーナビの経路案内やネットワークのルーティングに使われる。代表的な解法にダイクストラ法やベルマンフォード法がある。

重み付きグラフで、出発点から各頂点への最短経路を求めるアルゴリズム。すべての辺について距離の更新を頂点数−1回繰り返すことで、負の重みの辺があっても最短経路を求められ、負の閉路の存在も検出できる。ダイクストラ法より計算量は大きい。

頂点（ノード）と、頂点どうしを結ぶ辺（エッジ）で、ものどうしのつながりを表すデータ構造。辺に向きのある有向グラフと向きのない無向グラフがあり、プログラムでは隣接行列や隣接リストで表現する。路線網の最短経路探索や、ネットワークの構造の表現に使う。

出発点から各頂点への最短経路を、すべての辺について距離の更新（緩和）を頂点数－1回繰り返して求めるアルゴリズム。負の重みの辺があっても正しく求められ、もう1回更新して距離が変わるなら、たどるほど距離が減り続ける負の閉路があると判定できる。計算量はO(VE)で、ダイクストラ法より遅い。