ダイクストラ法 とは？

まさにカーナビの中身で使われているアルゴリズムだよ！街を「交差点（ノード）」と「道路（辺）」のグラフとして表して、出発地から目的地までの最短ルートを見つけるんだ

やり方はシンプルだよ。まず出発地の距離を0、他の全地点を「無限大」にする。次に「まだ確定していない中で一番距離が短い地点」を選んで確定する。そこから行ける隣の地点の距離を更新して、また一番近いものを確定…これを繰り返すだけだよ

そう、それが賢いところだよ。「一番近い未確定ノードを確定する」というルールのおかげで、無駄な探索を省けるんだ。優先度付きキューを使えば効率よく実装できるよ

道路の重み（距離やコスト）がマイナスだと正しく動かないんだ。「通ると距離が減る道」があるとアルゴリズムの前提が崩れてしまう。その場合はベルマン・フォード法という別のアルゴリズムを使うよ。あとA*アルゴリズムというダイクストラ法を改良したものもあって、ゲームAIではそちらが定番だね