読者です 読者をやめる 読者になる 読者になる

ダイクストラ法~線形探索~

Rubyダイクストラ法の実装を行います。
探索済みとなる要素は線形探索しています。
こちらのコードをrubyコードに変換することで実装させてもらいました。)

$MAX_V = 6
$INF = 100000

def dijkstra(s)
  cost = [
  [$INF, 2,    5,    $INF,  $INF,  $INF,  $INF],
  [2,   $INF,  4,    6,    10,   $INF,  $INF],
  [5,   4,    $INF,  2,    $INF,  $INF,  $INF],
  [$INF, 6,    2,    $INF,  $INF,  1,    $INF],
  [$INF, 10,   $INF,  $INF,  $INF,  3,    5],
  [$INF, $INF,  $INF,  1,    3,    $INF,  9],
  [$INF, $INF,  $INF,  $INF,  5,    9,   $INF]]

  d = []
  used = []
  d.fill($INF,0..$MAX_V)
  used.fill(false,0..$MAX_V)
  d[s] = 0
  
  while(1)
      v = -1
      for u in 0..$MAX_V do
          if !used[u] && (v == -1 || d[u] < d[v]) then
              v = u
          end
      end
      
      if v == -1 then
          break
      end
      
      used[v] = true
    
      for u in 0..$MAX_V do
          d[u] = d[u] < (d[v] + cost[v][u]) ? d[u] : (d[v] + cost[v][u])
      end
  end
  
  return d
end

print dijkstra(0)

実行結果です。途中のノード番号などを出力はしていません。

[0, 2, 5, 7, 11, 8, 16]
Complete(0)

線形探索部分が下記の部分です。
条件文は(ノードが確定しているかのフラグ && 未訪問 || 現在値よりも小さい)
と読めます。

      for u in 0..$MAX_V do
          if !used[u] && (v == -1 || d[u] < d[v]) then
              v = u
          end
      end

経路更新は下記の部分です。
対象すると経路(d[u])に対して、新規経路(d[v] + cost[v][u])の方が短いかどうか
を判定し、その結果を代入しています。
途中のノード番号を保持するならばここに追加コードが必要です。

      for u in 0..$MAX_V do
          d[u] = d[u] < (d[v] + cost[v][u]) ? d[u] : (d[v] + cost[v][u])
      end

今回は線形探索で実装しましたが、次はプライオリティキューを用いて実装したいです。