最短路問題を解く計算機を作った
1. 計算機を見る
https://heabiside.github.io/calculators/
ここから計算機を使うことができます。JSはその場しのぎ的に書いたのでコードはきれいじゃないです。
2. これはなに
ダイクストラ法とベルマンフォード法で最短路問題を解きます。
下の写真はベルマンフォード法で次のグラフの最短路問題(sスタート)を解いたときの見た目です。ループごとに最短路が更新される様子を表に出力しています。
3. 実装方針
簡単に書きます。実装で使ったアルゴリズムの大まかなコードは1のところのリンクにアクセスすれば見れます。
ベルマンフォードに関して言えば、JSでベルマンフォードを計算して、各ループごとにhtmlとして表にして出力しているだけです。
ダイクストラ法も似たような感じで実装しています。
ちなみにこの計算機のところのグラフはdotを使って作成しています。(テキストを書くだけでグラフを自動出力してくれて便利です。)
以上です。ここまで読んでいただきありがとうございます。
