class NgLib:: DijkstraGraph(Weight)

Overview

$n$ 頂点 $m$ 辺の重み付きグラフに対して、最短経路を求めます。

経路の復元も可能です。

このクラスは辺の重みが非負整数であるときのみ使えます。 辺の重みに非負整数以外を使いたい場合は nglib/graph/dijkstra を require してください。

Defined in:

nglib/graph/dijkstra.cr
nglib/graph/radix_dijkstra.cr

Constructors

Instance Method Summary

Constructor Detail

def self. new (n : Int ) #

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

graph = Dijkstra.new(n)

[ View source ]

Instance Method Detail

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

非負整数の重み $w$ の辺 $(u, v)$ を追加します。

directed が true の場合、 有向辺とみなして、$u$ から $v$ への辺のみ生やします。 

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

[ View source ]
def add_edge (u : Int , v : Int , w : Weight, directed : Bool = true ) #

非負整数の重み $w$ の辺 $(u, v)$ を追加します。

directed が true の場合、 有向辺とみなして、$u$ から $v$ への辺のみ生やします。 

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

[ View source ]
def shortest_path (start : Int , dest : Int ) #

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

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

[ View source ]
def shortest_path (start : Int ) #

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

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

[ View source ]
def shortest_path #

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

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

[ View source ]
def shortest_path_route (start, dest) #

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

route = graph.shortest_path_route(start: 2, dest: 0)
route # => [2, 7, 1, 0]

[ View source ]
def shortest_path_tree (start, directed : Bool = true ) : Array(Array(Int32)) #

始点 start から最短路木を構築します。

最短路木は start からの最短経路のみを残した全域木です。 

route = graph.shortest_path_route(start: 2, dest: 0)
route # => [2, 7, 1, 0]

[ View source ]
def size : Int32 #

[ View source ]