最短経路問題
深さ優先探索はグラフを探索するためのアルゴリズムです*1.注意書きの通り、細かいことを言うと面倒なのですが、以下ではグラフ上の二頂点間の連結性を判定するアルゴリズムだと思って説明を進めましょう. 定義 入力:グラフ 、始点 、終点 . 出力: と …
最短経路問題を解くアルゴリズム.ベルマンとフォードが共著の論文で一つのアルゴリズムを提案したわけじゃないようなのですが、なんでベルマン-フォード法って呼ぶのでしょうね?*1 定義 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への…
グラフ上の最短経路問題を解くアルゴリズム.エドガー・ダイクストラが 1959 年出版の論文で提案. 入出力 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への経路.すなわち、次を満たす頂点の列 (ただし ). 、 、 任意の について . 解…
あるいは最短経路探索問題. 定義 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への経路.すなわち、次を満たす頂点と辺の列 (ただし ). 、 、 任意の について . 解のコスト:経路に含まれる各辺のコストの和. 出力:コスト最小の解.…