(C)2000/STUDIO Septigram.
ダイクストラ(dijkstra)法による最短経路木のアプレット。大きい白丸が始点で、最短経路木が明るい赤で描かれる。
とある仕事で最短経路問題を解く必要があって、ダイクストラのアルゴリズムを調べた。情報処理系とか幾何系では有名なアルゴリズムらしいけど、機械制御科の私には目うろこでちょっと感動すらした。初めてクィックソートに触れた高校生のころの感動に近いものがあったのだ。このアルゴリズムは、グラフ問題に特有の高い応用性を備えていて、思考ルーチンなどに応用できる。
ダイクストラ法自体は(優れたアルゴリズムのほとんどがそうであるように)単純で、すべてのノードが接続されるまで、始点のノードに繋がるネットワークへの最短距離のアークを順次追加していくだけなのだ。それで最短経路木が作成される。ここの始点は、実は最短経路探索の時はゴールのノードにあたる。スタートのノードが木に追加された時点で、その木の根までの経路がスタートからゴールへの最短経路になる。
ちなみに動き回るノードを接続するアークはドローネ(delaunay)線図になっている。このサンプルのために、とあるプログラムから拾ってきたアルゴリズムを使用している。ドローネ線図は平面状に分散したノードをアークが交差しないように接続した図で、平面を三角形で分割することができるため、ちょっと前の3D画像に使用するポリゴン生成で活躍していた。ここで使用したアルゴリズムは計算に必要なバッファ領域がO(n2)なので、改良の余地がありそう。