Shortest-Path Problem

Graph Algorithm

"Shortest-Path Problem (最短路問題)"とは、
"最短路(shortest path)"を求める問題。


『vertex(頂点) u からvertex vへの最短路』とは
『経路重みが、最短路重みに等しい経路』。
　w(p) = \delta (u,v)。


※ここで、"辺重み","経路重み", "最短路重み"の定義は以下：

[辺重み]
　Edge(辺)を、実数値のWeight(重み)に変換する関数 w：w: E →R

[経路重み]
　経路 p = < v_0, v_1, ..., v_k> の 重みは、構成するEdgeの重みの和：
　 w(p)= \sum_{i=1}^{k} w(v_{i-1}, v_{i})

[最短路重み]
　vertex uからvertex vへの最短路重み \delta (u,v)は、次のように定義される
　\delta (u,v)
　 = min \{w(p): u -> v \} (uからvへの経路が存在するとき)
　 = \infty 　　　　　　　(uからvへの経路が存在しないとき)


[Reference]:
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)