[Ruby] 10行で書ける Dijkstra 法

  • ????????????????????

Dijkstra法はグラフ上の最短経路を求めるアルゴリズムです。このアルゴリズムの戻り値はある基点となるノードからその他のすべてのノードまでの距離の配列です。

解説はウェブ上にも豊富にあるので省略することにして、ここではどのくらい短いコード量で Dijkstra法を実装できるのか、という遊びをしてみます。仕様としては

  • 隣接リストではなく隣接行列を受け取る
  • ある二点間に辺が存在しない ⇔ 隣接行列の要素が負の値
  • ある辺の距離は隣接行列の正の要素で表現
  • 出力は指定した頂点からすべての頂点までの距離
  • 外部ライブラリを使用しない

くらいのものを考えましょう。

こんな感じになりました。

# Calculate shortest path from node o (to all nodes) on graph g

def dijkstra g, o
  (rec = Proc.new { |g,i,c|
    g[i].each_with_index { |a,j| c[j]=1,c[i]-a].max if c[j]<0 and a>=0 }
    c[i], k, cmin = -c[i], 0, -10**9
    return c if c.all?{ |e| e>=0 }
    c.each_with_index{ |cj, j| k, cmin = j, cj if cmin < cj and cj < 0  }
    return rec.call(g, k, c)
  }).call(g, o, (0..g.length-1).map{ |i| i==o ? 0 : -10**9})
end

そこそこコンパクトになった気がします。Dijkstra法は動的計画法の一種なので再帰を使ってかけます。Y-Combinator 使ってみようか、と思いましたが、またの機会にしました(汗

ほんとは1行で書けるかなーなんて妄想していたのですが、私の実力では無理っぽいです。こんなものを使う人はいないと思いますが、このコードは「遅い」ので注意してください。「遅い」というのは問題のサイズに対して理論的なスケーリング特性がないという意味です。その理由は本来は優先順位つきキューを使うべきところをリニアサーチに変更しているからです。現在のところ、Ruby の標準ライブラリには優先順位つきキューは存在しません。gem には depq というものが存在するようですが。

# Helper function
def al g, i, j, w=1
  g[i][j]=w
  g[j][i]=w
end
n=6
g=n.times.collect{ Array.new(n,-1)}

# adding links
al g, 0, 1, 5
al g, 0, 4, 4
al g, 0, 5, 2
al g, 1, 4, 2
al g, 1, 2, 6
al g, 2, 3, 4
al g, 3, 4, 2
al g, 3, 5, 6
al g, 4, 5, 3

# solve
p dijkstra g, 0 => [0, 5, 10, 6, 4, 2]
はてなブックマーク - [Ruby] 10行で書ける Dijkstra 法
Pocket