ダイクストラ法
アルゴリズム図鑑
に掲載の解説が多分いちばん直観的で分かりやすい
メリット
負の閉路
が存在しないケースにおいて、
ベルマンフォード法
よりも計算量を抑えて最短経路を求められる.
任意のノードから別のノードへと探索する際、リーチ可能な全ノードにアクセスして最小値をとるような方法を採ってるため.
デメリット
負のコストを含むグラフの場合、探索の深さKが限られているケースにおいて最短経路が正しく求まらないケースがある
負の閉路が存在する場合も、同様に最短経路は求まらない
従って、ダイクストラ法は
負のコストを含むグラフには使えない