【アルゴリズム】 最短路問題

最短経路問題

街1を始めとして街nまでがあるとする。そのとき、街1から各街の一番の近道を探すという時に使えるアルゴリズム。

ダイクストラ（Dijkstra）法というアルゴリズムを使っている。これはWikipediaにも載っていて、そこにあるGifアニメーションは動作原理が結構わかりやすい。

今回もCで書かれているソースをRubyに書きなおしただけ。サンプルソースのdijkstra.datを標準入力から読み取る。苦労したので、デバック用に差し込んだprintfなどもそのまま残しておこう。

以下の様な感じで実行する。dijkstra.datは、『C言語による最新アルゴリズム事典』のalgo.lzhの中にあるもの。

C:\\>ruby dijkstra.rb < dijkstra.dat

#!ruby -Ks

#
# 最短路問題
#

INT_MAX = 32768

NMAX = 100
$weight = Array.new(NMAX + 1){|i| Array.new(NMAX + 1) }
$n = 0;

START = 1

def readweight
  $n = gets.to_i
  if $n > NMAX
    $n = 0
    return
  end

  (1..$n).each {|i|
    (1..$n).each {|j|
      $weight[i][j] = INT_MAX
    }
  }

  while (l = gets and n = l.scan(/^([0-9]) ([0-9]) ([0-9])/)) and (n[0] ? n[0] : []).length == 3
    i, j, x = n[0].collect{|i| i.to_i }
    $weight[i][j] = $weight[j][i] = x
  end

  puts "データ weight(i, j)"

  (1..$n).each {|i|
    (1..$n).each {|j|
      if $weight[i][j] < INT_MAX
        printf "%3d", $weight[i][j]
      else
        printf " ∞"
      end
    }

    puts ""
  }
end

def main
  readweight
  visited = Array.new(NMAX + 1)
  distance = Array.new(NMAX + 1)
  prev = Array.new(NMAX + 1)

  (1..$n).each do |i|
    visited[i] = false
    distance[i] = INT_MAX
  end

  distance[START] = 0
  n_next = START

  begin
    i = n_next # ベースこれを起点にして可能な経路をたどる
    visited[i] = true
    min = INT_MAX

    (1..$n).each do |j|
      next if visited[j]
      if $weight[i][j] < INT_MAX and distance[i] + $weight[i][j] < distance[j]
        printf "i: %d j: %d distance[i]: %d distance[j]: %d weight: %d\\n", i, j, distance[i], distance[j], $weight[i][j]
        distance[j] = distance[i] + $weight[i][j] # 起点 + ベースの点からの距離
        p distance.slice(0..$n)
        prev[j] = i
      end

      if distance[j] < min
        printf "min: %d i: %d j: %d\\n", min, i, j
        min = distance[j] # 今現在の最短距離
        n_next = j # これが最短距離だった場合、次はこれが起点になる
      end
    end
  end while min < INT_MAX

  puts "点 直前の点 最短距離"
  (1..$n).each do |i|
    if i != START and visited[i]
      printf "%2d%10d%10d\\n", i, prev[i], distance[i]
    end
  end

  return 0
end

main

以下の様な出力になる。

データ weight(i, j)
 ∞  1 ∞ ∞  4
  1 ∞  3  1  3
 ∞  3 ∞  1 ∞
 ∞  1  1 ∞  1
  4  3 ∞  1 ∞
点 直前の点 最短距離
 2         1         1
 3         4         3
 4         2         2
 5         4         3

最初、「データ weight(i, j)」の表の読み方がよくわからなかった。いろいろ調べたところ、横が街nで縦が目的地の街になる。これはあくまでも、経路の距離（というかコスト、重み）を記しただけの表である。これだけを理解するだけで4～5日ほど取られた。

経路を調査する点は、とりあえず直接いける場所へ行ってみる。そのとき、かかったコストを点が今までかかったコストと足していく。そうした直接いける場所へのコストが一番小さいものが最短経路となる。

動作原理を理解するのに、dijkstra.rbの97行目にデバック用（配列distanceの中身）のpを差し込んでようやくわかった。

結局、これを理解するのに2週間ほどかかってしまった。結構大変だった。

これ以上に効率のいい、A*というアルゴリズムがあるらしい。

参考サイトなど

• http://coconut.sys.eng.shizuoka.ac.jp/ando/contr/hama08_ho.pdf
• http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95

2012/08/14 1:18