ベルマンフォードのアルゴリズムで実行される結果も逐次表示

離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃんということでやってみた。

pngファイルをアニメーションgifに変換するのはこんな感じで。この辺を参考に。

convert -geometry 320x500! -delay 150 -loop 0 bellman_ford_example_a_uniq*.png bellman_ford_example_a.gif

俺はRubyで書いたわけだけど、こんなことをやってるid:mickey24に「それRでできるよ!!」と言われそうである。

単一始点最短路問題に対するその他のアルゴリズム

ベルマンフォードのアルゴリズムは単一始点最短路問題に対するアルゴリズムの中では最も汎用的なものになっている。つまり

• 閉路があっても動く(閉路があったらfalseを返す)
• 負の辺があっても正常に動く

というようなアルゴリズムである。汎用性の代償として計算量はとなっている(Mはグラフの枝の本数、Nはノードの数)。そこで、扱うグラフを制限することでこの計算量を改善しようというのが

• ベルマンフォードのアルゴリズムの中でトポロジカルソートを用いて全頂点を走査するアルゴリズム
• ダイクストラのアルゴリズム

の二つである。

ベルマンフォードのアルゴリズムの中でトポロジカルソートを用いて全頂点を走査するアルゴリズム

ベルマンフォードのアルゴリズムの中で、各辺について緩和をするというところがある。「各辺について」ということろには順序は指定されておらず、ある意味ここがネックとなっている。なので、ここの走査する順番を考えてあげようというのがこのアルゴリズムである。図に書いてみると分かるが、ソースから深さ優先探索(でいいのかな。。。)をするように辺をたどっていくと効率よくできそうである(閉路がなければ)。ソースからのトポロジカルソートを考えて、その順序で、辺を走査していけばよいというのが「ベルマンフォードのアルゴリズムの中でトポロジカルソートを用いて全頂点を走査するアルゴリズム」である。

このアルゴリズムはトポロジカルソートによって改善されることになり、計算量はで動かすことができる。

ダイクストラのアルゴリズム

ダイクストラのアルゴリズムは辺の重みが全て非負であるグラフに対してうまく動く。ダイクストラのアルゴリズムでは始めにmin-優先度付きキューQを用意して、Vの全ての頂点を入れる。Qが空になるまで最小値の頂点uを取り出していく。uとuから出ていった先の頂点vを使って、緩和していくという流れになっている。Rubyによるダイクストラのアルゴリズムは昔やっている。

コード

本当はもっと完結なんだけど、アニメーションを吐き出させるためにごじゃごじゃとなってしまった。

# -*- coding: utf-8 -*-
require "rubygems"
require "graphviz"
require "pp"
require "set"
require 'logger'

# class for directed graph
class DirectedGraph
  attr_reader :nodes
  attr_reader :weights
  def initialize # initialization
    @nodes = []
    @weights = Hash.new{|h,k| h[k] = {}} # weights for edges
    @log = Logger.new(STDOUT) # logger
  end

  def add_node(v)
    @nodes.push v unless @nodes.include?(v)
  end

  def [](v, w)
    return @weights[Set.new [v, w]]
  end

  def []=(v, w, weight) # function to set the weight for the edge
    add_node(v)
    add_node(w)
    edge = {}
    edge[v] = w
    @weights[edge] = weight
  end

  def bellman_ford(s, file="")
    # initializationp
    d = {} # store minimum cost
    pi = {} # store predecessor
    i = 0
    @nodes.each{|n|
      d[n] = 1/0.0
      pi[n] = nil
    }
    d[s] = 0
    k = 0
    (@nodes.length - 1).times do
      prev_d = d.clone; prev_pi = pi.clone
      @weights.each_pair{|e, w|
        tmp_d = d.clone; tmp_pi = pi.clone
        u = e.keys[0]
        v = e.values[0]
        # relax
        if d[v] > d[u] + w
          d[v] = d[u] + w
          pi[v] = u
        end
        convert2graphViz_each_iteration(d, pi, file+i.to_s) if @log.debug?
        i += 1
        if @log.debug?
          print "#{i} #{k} : "
          pp d
          # pp pi
          convert2graphViz_each_iteration(d, pi, file+"_uniq"+sprintf("%02d", i).to_s) if (tmp_d != d) || (tmp_pi != pi)
        end
      }
      break if (prev_d == d) && (prev_pi == pi)
      k += 1
    end
    # judge whether the graph includes negative cycle
    @weights.each_pair{|e, w|
      u = e.keys[0]
      v = e.values[0]
      if d[v] > d[u] + w
        return false
      end
    }
    # output the shortest-path weight from s to v (v \in V) and 
    # shortest-path itself if the graph doesn't include negative cycle
    if @log.debug?
      (@nodes - [s]).each{|n|
        predecessor = pi[n]
        path = [n]
        while predecessor != s
          path.unshift predecessor
          predecessor = pi[predecessor]
        end
        path.unshift s
        puts "Shortest-path weight from #{s} to #{n} and shortest-path itself are as follows."
        puts "#{d[n]} : #{path.join(" -> ")}" # cost : path
      }
    end
    return true
  end

  def set_log_level(level)
    @log.level = level
  end

  def convert2graphViz_each_iteration(d, pi, file)
    option = {:output => "png", :file => "#{file}.png"}
    g = GraphViz.new("G", option)
    @nodes.each{|node|
      eval("g.node#{node}(:label => \"#{node}(#{d[node]})\")")
    }
    @weights.each_pair{|key, value|
      if pi[key.values[0]] == key.keys[0]
        eval("g.add_edge(g.node#{key.keys[0]}, g.node#{key.values[0]}, :label => #{value}.to_s, :color => \"red\")")
      else
        eval("g.add_edge(g.node#{key.keys[0]}, g.node#{key.values[0]}, :label => #{value}.to_s)")
      end
    }
    g.output
  end
  def convert2graphViz(option) 
    # function to plot the graph
    # option must be a hash
    g = GraphViz.new("G", option)
    @nodes.each{|node|
      g.add_node(node)
    }
    @weights.each_pair{|key, value|
      g.add_edge(g.add_node(key.keys[0]), g.add_node(key.values[0]), :label => value.to_s)
    }
    return g
  end
end

g = DirectedGraph.new

g["a","b"] = 6
g["a","c"] = 7
g["b","d"] = 5
g["b","e"] = -4
g["b","c"] = 8
g["c","d"] = -3
g["c","e"] = 9
g["d","b"] = -2
g["e","d"] = 7
g["e","a"] = 2

g.set_log_level(Logger::DEBUG)
pp g.bellman_ford("a", file="graph/bellman_ford_example_a")

参考

• アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)