Nim言語でダイクストラ法を書いてみる

はじめに

ダイクストラ法というものをご存知でしょうか?
ざっくりいうと、目的地までの最短コースを探すときに使うアルゴリズムの一つです。

それを性懲りもなくNimで実装してみましょう。

ダイクストラ

以下のサイト様がわかりやすいかと思います。
https://products.sint.co.jp/topsic/blog/dijkstras-algorithm

ざっくりいうと、次の目的地までのコストを計算するアルゴリズムの一つです。
あれ?さっきも書いた?
コストというのは、現実世界で言う「信号」だとか「登道」だとかそういった時間がかかるものになります。

ダイクストラ法のコード

では早速コードです。

proc dijkstra*(edges: seq[seq[seq[float64]]], vertexNum: int): seq[float64] =
  # 道のりとして使う変数を初期値として大きな値をセット
  var destination: seq[float64]
  for i in 0..vertexNum - 1:
    destination.add(99999999.0)
  
  # 配列の最初はスタート地点なのでコストを0にする
  destination[0] = float64(0)

  var queue: seq[int]
  for i in 0..vertexNum - 1:
    queue.add(i)
  
  while len(queue) > 0:
    # コストが最小限の頂点(頂点)を見つける
    var r = queue[0]
    for i in queue:
      if destination[i] < destination[r]:
        r = i

    let u = queue[queue.find(r)]
    queue.delete(queue.find(r))

    for edge in edges[u]:
      if destination[int(edge[0])] > (destination[u] + edge[1]):
        destination[int(edge[0])] = destination[u] + edge[1]

    
  return destination

与えられた目的地とそのコストから、コストが最小になるように道のりを出していきます。
実際に動作させてみましょう。

動作付きのコード

proc dijkstra*(edges: seq[seq[seq[float64]]], vertexNum: int): seq[float64] =
  ##
  ## edges: 辺の終点と個数のリストを渡します
  ## vertexNum: 頂点の数を渡します
  ## 

  # 初期値として大きな値をセット
  var destination: seq[float64]
  for i in 0..vertexNum - 1:
    destination.add(99999999.0)
  
  # 配列の最初はスタート地点なのでコストを0にする
  destination[0] = float64(0)

  var queue: seq[int]
  for i in 0..vertexNum - 1:
    queue.add(i)
  
  while len(queue) > 0:
    # コストが最小限の頂点(頂点)を見つける
    var r = queue[0]
    for i in queue:
      if destination[i] < destination[r]:
        r = i       # コストが小さい頂点が見つかると更新

    let u = queue[queue.find(r)]
    queue.delete(queue.find(r))

    for edge in edges[u]:
      if destination[int(edge[0])] > (destination[u] + edge[1]):
        destination[int(edge[0])] = destination[u] + edge[1]

    
  return destination


const dijkstraTestData = @[
    @[@[1.0, 4.0], @[2.0, 3.0]],                    # 頂点A(0.0)からの辺のリスト[[頂点Bへ行ける, コストは4.0], [頂点Cへ行ける, コストは3.0]]
    @[@[2.0, 1.0], @[3.0, 1.0], @[4.0, 5.0]],       # 頂点B(1.0)からの辺のリスト[[頂点Cへ行ける, コストは1.0], [頂点Dへ行ける, コストは1.0], [頂点Eへ行ける, コストは5.0]]
    @[@[5.0, 2.0]],                                 # 頂点C(2.0)からの辺のリスト[[頂点Fへ行ける, コストは2.0]]
    @[@[4.0, 3.0]],                                 # 頂点D(3.0)からの辺のリスト[[頂点Eへ行ける, コストは3.0]]
    @[@[6.0, 2.0]],                                 # 頂点E(4.0)からの辺のリスト[[頂点Gへ行ける, コストは2.0]]
    @[@[4.0, 1.0], @[6.0, 4.0]],                    # 頂点F(5.0)からの辺のリスト[[頂点Eへ行ける, コストは1.0], [頂点Gへ行ける, コストは4.0]]
    @[]                                             # 頂点G(6.0)からの辺のリスト(ゴール)
  ]

let dijkstraResult = dijkstra(dijkstraTestData, 7)
assert dijkstraResult == @[0.0, 4.0, 3.0, 5.0, 6.0, 5.0, 8.0]

このような感じです。
assetの部分は、頂点Aから各頂点に向かったときの最小のコストとなっております。
図にすると以下のようになります。

f:id:taanatsu:20210930182002p:plain

今回だとA→C→F→E→Gと進むのが一番コストが少なそうですね!
このように利用します。

あとがき

結構昔に勉強したので思い出すのに時間がかかりました……
ヒープを使った計算式の最適化とか、ダイクストラを応用したA*(エースター)探索なんてのもありますね。
まだまだ奥が深い領域です。