class NgLib::BfsGraph

• NgLib::BfsGraph
• Reference
• Object

Overview

$n$ 頂点 $m$ 辺からなるグラフに対して、幅優先探索によって最短経路を求めます。

経路の復元も可能です。

Defined in:

Constructors

• .new(n : Int)

  $n$ 頂点 $0$ 辺からなるグラフを作成します。

Instance Method Summary

• #add_edge(u : Int, v : Int, directed : Bool = true)

  辺 $(u, v)$ を追加します。

• #graph : Array(Array(Int32))
• #shortest_path(start : Int, dest : Int)

  始点 start から終点 dest への最短経路長を返します。

• #shortest_path(start : Int)

  始点 start から各頂点への最短経路長を返します。

• #shortest_path

  全点対間の最短経路長を返します。

• #size : Int32

Constructor Detail

graph = BfsGraph.new(n)

Instance Method Detail

graph = BfsGraph.new(n)
graph.add_edge(u, v)                 # => (u) <---w---> (v)
graph.add_edge(u, v, directed: true) # => (u) ----w---> (v)

dist = graph.shortest_path(start: 2, dest: 0)
dist # => 12

dist = graph.shortest_path(start: 2)
dist # => [3, 8, 0, 7, 1]

dists = graph.shortest_path
dists # => [[0, 1, 3], [1, 0, 2], [1, 1, 0]]