class NgLib::FloydWarshallGraph(T)

Overview

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

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

Defined in:

nglib/graph/floyd_warshall.cr

Constructors

Instance Method Summary

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]