ダイクストラ法をPythonで試してみる

最近就活で、ある企業のプログラミングテストを受けることになったんだけど最短経路問題が出るらしい。

正直アルゴリズムとかは全く勉強したことがなくて、そろそろちゃんとやらなきゃとちょうど思ってた頃だった。ほんとに

そんなわけで最短経路問題の解法であるアルゴリズムの一つ、ダイクストラ法というものを試してみた。

ネットにいろいろ説明が乗っているものの、ちょっとよくわからん。。。

と思ってたんだけど、YouTubeでめっちゃわかりやすい動画を見つけた。

これを参考にPythonで実装してみた。コードが汚いけど一応GitHubに上げてあります。

試しにネットで拾った図で解いてみた。今回使うのはこの図

そしてこれが様々な始点と終点で試した結果。最短経路らしい道を計算してくれているのが分かる。

乗換案内とかは内部でこういうアルゴリズムを使って最安ルートとかを計算しているらしい。

最初に考えた人はすごいなあ