本履歴

購入した古本の履歴と時々プログラミング

Pure Implementation of Dijkstra's Shortest Path Algorithm with Priority Queue in Ruby

プログラム言語 Ruby での純粋ダイクストラ最短経路アルゴリズム(優先順位付きキュー利用)です。O(m*log(n))の実行時間です(n:ノード数、m:辺の数)。
外部ライブラリなどに依存していないため、このままコピペすれば競技プログラミングで使えると思います。Ruby1.9.3..Ruby2.3.0で動きました。1.9.3は2.3.0の1.8倍時間がかかりました。
一応、AOJのGraph II - Single Source Shortest Path II(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C)とAtCoderのABC#035 D - トレジャーハント(http://abc035.contest.atcoder.jp/tasks/abc035_d)は通ったので、Rubyのバージョンが高い&&寛容(?!)なオンラインジャッジ(通常時間制限の数倍余裕くれるところ)では通ると思います。しかし、C++なんかと同じタイム制限のところではまず通らないと思います。やはり十数倍..数十時間がかかるようです。

利用上の注意点は、edges, costs共に0-indexedに加工して下さい。問題文で町に番号が1..nと割り振られーとかある場合に注意が必要。またアルゴリズムの性質上負のコストがあるとうまく動きません。プログラムはsから到達できる全ノードを巡った後最小コスト配列を返しますが、目的地がeと明確になっているのなら、visited[e]=trueになったら即終了したほうが速い。競技プログラミングの性質上、凶悪入力にも打ち勝たないといけないのであまり意味はないかもですが。
precursorには、アンコメントの後、最小コストのルートの1個前のノードが入ります。e=precursor[e] while e で後ろから前に辿れます。

以上です。よろしくお願い致します。

#!ruby

#Last Updated at 04/06/2016
#最短経路問題をダイクストラwith優先順位付きキューアルゴリズムで解く
#入力:
#edges: nノードの隣接リスト(0-indexed) e.g. [[1,2,3],[5],[0,1],...] means
# node 0からの辺はnode 1,2,3へ出ている、node 1からはnode 5のみ等々
#costs: コスト(辺の長さなど)、costs[x][y]で正数を返せばOK。
#s: 開始点。0..n-1
#出力:
#sからの最小コストのリスト dijkstra(edges,costs,s)[e]でs-e間の最小コスト
#到達出来ない点はINF
#経路を知りたい場合はprecursorのアンコメントする。precursor[k]でnode kの前のノードがわかる

INF = 1 << 60 #プログラム簡易化のため利用。全コスト和より大きい値にする

#O(m*log n) where m:辺の数
def dijkstra(edges, costs, s = 0)
	#初期化
	n = edges.size #ノード数
	node_to_pq_id = Array.new(n, nil) #nodeとpq.push時に割与えられたkeyの対応を管理
	#precursor = Array.new(n,nil)
	d = Array.new(n, INF) #sから別ノードまでの(これまで分かった)最短コスト
	d[s] = 0
	pq = PriorityQueue.new
	edges[s].each{|u|
		id = pq.push(Node.new(costs[s][u], u))
		d[u] = costs[s][u]
		node_to_pq_id[u] = id
		#precursor[u] = s
	}
	visited = Array.new(n, false) #既に訪れたか?
	visited[s] = true

	#本体処理
	until pq.empty?
		min = pq.pop
		cost,v = min.cost, min.node
		visited[v] = true
		d[v] = cost
		edges[v].each{|w|
			next if visited[w]
			next if d[w] <= cost + costs[v][w]
			#precursor[w] = v
			d[w] = cost + costs[v][w]
			#ノードwまでの冗長だったコストをよりお得なv経由コストにPQ内で変更
			if node_to_pq_id[w]
				pq.change_key(node_to_pq_id[w], Node.new(d[w], w))
			else
				#PQに初めてノードを入れる場合
				id = pq.push(Node.new(d[w], w))
				node_to_pq_id[w] = id					
			end
		}
	end
	d
	#[d, precursor]
end

#PQ用データ構造、コード簡易化のため
class Node
	attr_reader :cost, :node
	def initialize(cost, node)
		@cost = cost
		@node = node
	end

	def <= other
		@cost <= other.cost
	end

	def < other
		@cost < other.cost
	end

	def >= other
		@cost >= other.cost
	end

	def > other
		@cost > other.cost
	end
end

#Last Updated at 04/06/2016

#優先順位付きキュー
#ストアするデータは<=>で比較可能でなければならない
#小さい順か大きい順かは”符号を逆に”コメント箇所を変更
class PriorityQueue
  attr_reader :elements

  def initialize
    @elements = [nil] #ダミー。1-indexedにするため
    @position = {} #idのデータが@elementsのどこにあるかindexを返す
    @id = 0 #付与するid。1ずつインクリメント
  end

  #PQにデータを追加。付与されるidはchange_keyするときに指定する
  #つまり3を2回追加してもidは別になる
  #change_keyしない時は@position,@idの処理は全て不要
  #O(log n)
  def add(element)    
    @id += 1
    @elements << [element, @id]
    @position[@id] = size
    bubble_up(size)
    @id
  end

  #最小(大)値をPQから取り出し返す
  #O(log n)
  def pop
    exchange(1, size)
    max = @elements.pop
    bubble_down(1)
    max.first
  end

  #id(add時に付与される整数)による値の変更
  #値では動作できない(同じ値が入ることがあるため)
  #成功:self、失敗:nil
  #O(log n)
  def change_key(target_id, new_element)
    index = @position[target_id]
    return nil unless index
    if @elements[index].first <= new_element #符号を逆に
      @elements[index][0] = new_element
      bubble_down(index)
    else
      @elements[index][0] = new_element
      bubble_up(index)
    end
    self
  end

  #ストアされているデータ数
  def size
    @elements.size - 1
  end 

  def empty?
  	size == 0
  end

  alias :push :add
  alias :<< :add
  alias :length :size
private

  def bubble_up(index)
    parent_index = (index / 2)

    return if index <= 1
    return if @elements[parent_index].first <= @elements[index].first #符号を逆に

    exchange(index, parent_index)
    bubble_up(parent_index)
  end

  def bubble_down(index)
    child_index = (index * 2)

    return if child_index > size

    not_the_last_element = child_index < size
    left_element = @elements[child_index]
    right_element = @elements[child_index + 1]
    child_index += 1 if not_the_last_element && right_element.first <= left_element.first #符号を逆に

    return if @elements[index].first <= @elements[child_index].first #符号を逆に

    exchange(index, child_index)
    bubble_down(child_index)
  end

  def exchange(source, target)
    @position[@elements[source].last], @position[@elements[target].last] = target, source
    @elements[source], @elements[target] = @elements[target], @elements[source]
  end
end

if __FILE__ == $0
  n = 120000
  m = 500000
  bridged = {}
  costs = Array.new(n){Hash.new}
  edges = n.times.map{|i|
    if i == 0
      costs[i][1] = i
      bridged[[0, 1]] = true
      [1]
    elsif i == n - 1
      costs[i][n - 2] = n - 2
      bridged[[n - 1, n - 2]] = true
      [n - 2]
    else
      costs[i][i - 1] = i - 1
      costs[i][i + 1] = i
      bridged[[i, i - 1]] = true
      bridged[[i, i + 1]] = true
      [i-1, i+1]
    end
  }

  m.times{
    i, j = rand(n), rand(n)
    next if i == j
    next if bridged[[i, j]]
    edges[i] << j
    costs[i][j] = rand(n)
  }

  p dijkstra(edges, costs).last
end

ruby-prof

 %self      total      self      wait     child     calls  name
 10.76      7.970     3.695     0.000     4.275  1930414   PriorityQueue#exchange
 10.60      3.642     3.642     0.000     0.000 18678231   Array#[]
  6.42      3.806     2.206     0.000     1.599  3920171   PriorityQueue#size
  5.62      2.239     1.931     0.000     0.309  4960817   Hash#[]=
  5.08      4.941     1.744     0.000     3.197        3   Integer#times
  4.92      2.387     1.689     0.000     0.698  3750646   Node#<=
  4.48      1.540     1.540     0.000     0.000  7557191   Array#first
  2.98      1.023     1.023     0.000     0.000  4469026   Array#[]=
  2.77      4.905     0.953     0.000     3.952   120000   Array#each
  2.68      0.922     0.922     0.000     0.000  4520167   Fixnum#-
  2.48      0.851     0.851     0.000     0.000  4465190   Fixnum#<=
  2.31      0.793     0.793     0.000     0.000  3920172   Array#size
  2.24      0.770     0.770     0.000     0.000  3860829   Array#last