もう一人のY君

主にiPhoneのショートカットアプリのレシピやTipsなどを書いています. たまに数学の記事も書きます.

もう一人のY君 MENU  MENU

【グラフ理論】最短経路を求めるアプリ「Dijkstra Calculator」

180401_06

 数学におけるグラフ理論の一つ「最短経路」を求めることができるアプリです.

 概念自体は特に難しいものではなく, 簡単に言えば「どの道を進めば最短で目的地へたどり着くか」という問題であり, 地図サービスの経路探索にも使われいる身近なものです.

 

Dijkstra Calculator

Dijkstra Calculator

  • Peewah SAS
  • 教育
  • 無料

※価格は記事執筆時のものです. 現在の価格はApp Storeから確認ください.

 レビュー時のバージョン : v1.0

 

スポンサーリンク

 

 

目的地までの最短経路を計算

180401_07

 経路探索に必要なのは「ノード」と言われる円と「エッジ」と言われる線(今回は方向付きなので「有向グラフ」です)の2つです.

 まず画面上をシングルタップするとアルファベット付きの円が出てきます, これが「ノード」です.

 

 

180401_08

 エッジはノード同士を結びつける役割を果たします.

 例えばノードaからノードbにエッジを結びたい場合はノードaをスワイプしてノードbに重ね合わせます.

 指を離すと "Create edge" というポップアップが表示されるので "Cost" に「重み」に相当する数字(マップで言えば2地点a,bの距離のようなもの)を入力します.

 

 

180401_09

 これでノードaからノードbにエッジが追加されました.

 エッジが一つでも存在すると画面下に "Calculate" が表示されます.

 

 

ノード・エッジの削除

180401_10

 ノードは長押しすると画面下に×アイコンが表示されるので, ここに移動して指を離すことで削除されます.

 

 

180401_13

 またエッジはコストが表示されている部分をタップします.

 コストを編集するか, 削除する場合は "Delete" をタップします.

 

 

計算

180401_11

 グラフを作成したら画面下の "Calculate" をタップします.

 どのノードからどのノードまでの経路にするかを指定します.

 

 

180401_12

 OKをタップすれば指定した出発点のノードから終点のノードまでの経路のうち, 最もコストが少ない経路を緑色で表示します.

 

 

180401_18

 なお合計コストが全く同じ経路が複数ある場合は, 通るノードに書かれているアルファベットが若いものが対象となるようです.

 

 URLスキームは今のところ確認できませんでした.

 

 

URLスキームについてはこちら

[Search]iPhone URLスキーム -The theoryの戯言

iPhoneのURLスキームを検索して一覧表示できます. リクエストは内容に応じてお答えします.