class NgLib:: FloydWarshallGraph(T)

NgLib::FloydWarshallGraph(T)
Reference
Object

Overview

ワーシャル・フロイド法の実装です。

（負を含む）重み付きグラフに対して、全点対最短経路長が $O(V^3)$ で求まります。

Defined in:

nglib/graph/floyd_warshall.cr

Constructors

.new (matrix : Array(Array(T | Nil) | Array(T)))

隣接行列に従ってグラフを作ります。
.new (mat : Array(Array(T | Nil)))

隣接行列に従ってグラフを作ります。
.new (n : Int)

$n$ 頂点 $0$ 辺のグラフを作ります。

Instance Method Summary

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

重みが $w$ の辺 $(u, v)$ を追加します。
#mat : Array(Array(T | Nil))
#shortest_path

全点対最短経路長を返します。
#size : Int32

Constructor Detail

def self. new (matrix : Array(Array(T | Nil) | Array(T))) #

隣接行列に従ってグラフを作ります。

nil は辺が存在しないことを表します。無限大の重みを持つ辺と捉えても良いです。

mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
NgLib::FloydWarshallGraph(Int32).new(mat)

[ View source ]

def self. new (mat : Array(Array(T | Nil))) #

隣接行列に従ってグラフを作ります。

nil は辺が存在しないことを表します。無限大の重みを持つ辺と捉えても良いです。

mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
NgLib::FloydWarshallGraph(Int32).new(mat)

[ View source ]

def self. new (n : Int ) #

$n$ 頂点 $0$ 辺のグラフを作ります。

n = 10
NgLib::FloydWarshallGraph(Int64).new(n)

[ View source ]

Instance Method Detail

def add_edge (u : Int , v : Int , w : T, directed : Bool = true ) #

重みが $w$ の辺 $(u, v)$ を追加します。

directed が true である場合、有向辺として追加します。

n, m = read_line.split.map &.to_i
graph = NgLib::FloydWarshallGraph.new(n)
m.times do
  u, v, w = read_line.split.map &.to_i64
  u -= 1; v -= 1 # 0-index
  graph.add_edge(u, v, w, directed: true)
end

[ View source ]

def mat : Array(Array(T | Nil)) #

[ View source ]

def shortest_path #

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

どのような経路を辿っても到達できない場合は nil が格納されます。

mat = [[0, 3, 1], [-2, 0, 4], [nil, nil, 0]]
graph = NgLib::FloydWarshallGraph.new(mat)
d = graph.shortest_path # => [[0, 3, 1], [-2, 0, -1], [nil, nil, 0]]
d[0][1]                 # => 3  (i から j への最短経路長)

[ View source ]

def size : Int32 #

[ View source ]