dijkstra.rb

module Dijkstra

  # ノード全体を格納するクラス
  class Nodes
    def initialize
      @done = false
      @map = {}
    end

    def add id, edges_to
      node = Node.new(id)
      node.edges_to = edges_to
      @map.store(id, node)
    end

    def get(id)
      return @map[id]
    end

    def each &block
      return @map.each_value &block
    end

    def size
      return @map.size
    end

    attr_accessor :done

  end


  # ノード情報を格納するクラス
  class Node
    def initialize id
      @id = id
      @from = id
    end

    attr_accessor :id, :edges_to, :done, :cost, :from
  end


  # コストを格納するクラス
  class Edges
    def initialize(num_of_nodes)
      @edges = Array.new(num_of_nodes).map{Array.new(num_of_nodes, -1)}
    end

    # (i,j) のエッジにかかるコストを設定する
    def addCost(i, j, cost)
      @edges[i][j] = cost
    end

    # (i,j) のエッジにかかるコストを返す
    def getCost(i, j)
      return @edges[i][j]
    end

  end


  # アルゴリズム実行
  def dijkstra(nodes, edges, start)
    if start < 0 || nodes.size <= start
      raise "Size error -- start: #{start}"
    end

    # 初期化
    nodes.each do |node|
      node.done = false
      node.cost = -1
      node.from = -1
    end
    nodes.get(start).cost = 0  # スタートノードのコストは 0
    nodes.get(start).from = start


    while true
      # 確定ノードを探す
      doneNode = nil # 確定ノード
      nodes.each do |node|
        if node.done || node.cost < 0
          next
        end
        if doneNode == nil || node.cost < doneNode.cost
          doneNode = node
        end
      end

      # 確定していないノードがなくなれば終了
      if doneNode == nil
        break
      end

      # 確定フラグを立てる
      doneNode.done = true

      # 接続先ノードの情報を更新する
      doneNode.edges_to.each do |j|
        i = doneNode.id

        cost = doneNode.cost + edges.getCost(i,j)

        if nodes.get(j).cost < 0 || cost < nodes.get(j).cost then
          nodes.get(j).cost = cost
          nodes.get(j).from = i
        end

      end

    end

    nodes.done = true

  end


  # ゴールまでのルートを検索する
  #     input:
  #         goal ゴール地点の id
  #     return: goal までの id列
  def trace_route(nodes, goal)
    if goal < 0 || nodes.size <= goal
      return []
    end

    current = nodes.get(goal)
    route = Array.new

    while current.id != current.from
      route << current.id
      current = nodes.get(current.from)
    end
    route << current.id

    return route.reverse
  end


  # ゴールまでのコストを算出する
  def count_cost(nodes, goal)
    if goal < 0 || nodes.size <= goal
      return -1
    end

    if !nodes.done
      return -1
    end

    return nodes.get(goal).cost
  end


  module_function :dijkstra, :trace_route, :count_cost

end


if $0 == __FILE__ then

  # ノードの定義
  nodes = Dijkstra::Nodes.new

  # node(id, edges_to)
  nodes.add(0, [1, 2, 3])
  nodes.add(1, [0, 3, 4])
  nodes.add(2, [0, 3, 5])
  nodes.add(3, [0, 2, 1, 4])
  nodes.add(4, [1, 3, 5])
  nodes.add(5, [2, 4])


  # エッジのコスト行列
  edges = Dijkstra::Edges.new(nodes.size)

  # edges(from_id, to_id, cost)
  edges.addCost(0,1,2); edges.addCost(0,2,5); edges.addCost(0,3,4)
  edges.addCost(1,0,2); edges.addCost(1,3,3); edges.addCost(1,4,6)
  edges.addCost(2,0,5); edges.addCost(2,3,2); edges.addCost(2,5,6)
  edges.addCost(3,0,4); edges.addCost(3,2,2); edges.addCost(3,1,3); edges.addCost(3,4,2)
  edges.addCost(4,1,6); edges.addCost(4,3,2); edges.addCost(4,5,4)
  edges.addCost(5,2,6); edges.addCost(5,4,4)



  start = 0
  goal = 5


  puts "Route #{start} -> #{goal}: "
  Dijkstra.dijkstra(nodes, edges, start)
  route = Dijkstra.trace_route(nodes, goal)
  p route
  cost = Dijkstra.count_cost(nodes, goal)
  puts "cost: #{cost}"


  start = 4
  goal = 0

  puts "Route #{start} -> #{goal}: "
  Dijkstra.dijkstra(nodes, edges, start)
  route = Dijkstra.trace_route(nodes, goal)
  p route
  cost = Dijkstra.count_cost(nodes, goal)
  puts "cost: #{cost}"


end