はじめに

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

それを性懲りもなく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]