Shortest paths by BFS (and DFS)

今日は久しぶりに楽しい一日を過ごした。その理由は、一日中頭の体操をしていたから。
DFSや(たぶん)BFSで、複数の最短経路*1を出せそうだと分かったので、実際に実験をしてみた。
色々考えて見つけた方法は、vertexでなくてedgeで探索木を構築すること。
これって、昔、研究室で学んだgSpanのアイデアに似ている。
ちなみに、探索木を完全に構築すると、最短経路だけでなく、全ての可能な経路を見つけたことになる。
しかし、とても時間がかかるので、深さを制限するとそれなりに使えることが分かった。
実際の実装は、ruby + rgl + Boost Graph Library. rubyで書くと非常に簡単に書ける。
pseudo-codeとほとんど変わらない。
せっかくなので、BFSと今回のアルゴリズムのpseudo-codeを載せておく。
色をつけるところ(color[])をvertexからedgeに変えたことと、
一つ前のvertexを覚えておいているのがポイント。
よく考えてみると、BFSに限定せずにDFSでもどちらでもよさそう。

# Original BFS pseudo-code from Boost Graph Library,
# http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/breadth_first_search.html
# This algorithm searches all vertices.
BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE
    d[u] := infinity
    p[u] := u
  end for
  color[s] := GRAY
  d[s] := 0
  ENQUEUE(Q, s)
  while (Q != Ø)
    u := DEQUEUE(Q)
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY
        d[v] := d[u] + 1
        p[v] := u
        ENQUEUE(Q, v)
      else
        if (color[v] = GRAY)
          ...
        else
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)

# Edge colored BFS by tadakado
# This algorithm searches all edges.
# This can be apply for finding all possible
# paths of specific two vertices, s and e.
# For this purpose, you can find all paths by
# reversing the tree and following paths from
# e to s. You can use not only BFS but also DFS.
EdgeBFS(G, s)
  d := Ø
  tree := Ø
  for each edge (u,v) in E[G]
    color[(u,v)] := WHITE
  end for
  color[(0,s)] := GRAY
  d[(0,s)] := 0
  ENQUEUE(Q, s)
  ENQUEUE(P, 0)
  while (Q != Ø)
    u := DEQUEUE(Q)
    t := DEQUEUE(P)
    for each vertex v in Adj[u]
      if (color[(u,v)] = WHITE)
        color[(u,v)] := GRAY
        d[(u,v)] := d[(t,u)] + 1
        tree[(u,v)] := 1
        ENQUEUE(Q, v)
        ENQUEUE(P, u)
      else
        if (color[(u,v)] = GRAY)
          ...
        else
          ...
    end for
    color[(t,u)] := BLACK
  end while
  return (d, tree)

*1:似た問題にk-th shortest path problemというのがあることを後から知った