1. gw_dijkstra.exe の使用法

【概要】

ネットワークを構成するグラフにおいて、開始ノード(インデックス [0] のノード)を起点として、個々のノード迄の最短経路を求める

  1. gw_dijkstra.exe は、最短経路探索アルゴリズムを示すデモです
    　
  2. gw_dijkstra.exe を起動すると、自動的に 25個 (5 * 5) のノードを持つグラフが表示される

    各エッジに記入されている数字は Weight です。左下がスタート・ノードで、その値が 0 です。例えば、スタート・ノードの左にある４つのノードの値は順に N1[26], N2[93], N3[124], N4[207] です。

    各ノードの値は経路に沿って Weight を加算した合計です。

    ・このアプリは、電車の乗換え検索に対応させることができます。
    例えば、横方向が地下鉄の路線で、縦方向が JR の路線とし、横と縦が交差するノードが乗換え駅に対応します。エッジの Weight は駅間の走行時間 (分) に対応します。
    最寄り駅 (スタート・ノード) から目的の駅 (ゴール・ノード) に至る最短時間の経路を求めることが出来ます。

  3. スタート・ノード N0[0] からノード N6[29] に至る経路は、次の２通りある

    ・N0[0] -> N5[19] -> N6[29] ...... この経路の Weight の累計は 84 (= 19 + 65)
    ・N0[0] -> N1[26] -> N6[29] ...... この経路の Weight の累計は 29 (= 26 + 3)

    最終的に Weight の累計の小さい方を、このノードの値とするので、29 となる。

  4. 上記の手順で、全てのノードの Weight の累計を計算すると、右上のゴール・ノードの累計は 247 となる。スタート・ノードからゴール・ノードに至る最短経路は赤い線のようになります。


  5. ノード N8[121] の上で右クリックして、"delete" を選ぶと、スタート・ノードからゴール・ノードに至る最短経路は変更される。


  6. ノード N14[255] に至る経路は、左のノード N13[226] からと、下のノード N9[247] からの２通りです。下にある小さい BOX を上方にスライドさせて、Weight を 8 --> 34 に変更すると、ノード N14[255] に至る最短経路が変更される。

    　　　　　 左からの経路：226 + 54 = 280 .... こちらが最短となる
    　　　　　 下からの経路：247 + 34 = 281



  7. 別なグラフを自動生成して、最短経路を求める

    　　 メニューの "Graph-> Create-> random planar" を選ぶ
    　　 ダイアログが現れるので、以下の設定をする
    　　　　　　　 nodes = 12
    　　　　　　　 edges = 20
    　　　　　　　 layout= orthogonal


  8. 12個のノードを持つグラフが現れ、スタート・ノード [0] から各ノードに至る最短経路が太い青色のエッジで描かれる。[2147483647] と言う大きな値を持つノードはスタート・ノードから至る経路がない孤立したノードです。