class

Collections::WeightedGraph(T, W)

A graph whose edges carry weights, with Dijkstra shortest-path search built on PriorityQueue. T is the node/value type (any hashable value) and W is the weight type (a non-negative numeric type such as Int32 or Float64).

Edges are undirected by default; pass directed: true to add a one-way edge.

graph = Collections::WeightedGraph(String, Int32).new
graph.add_edge("a", "b", 1)
graph.add_edge("b", "c", 2)
graph.shortest_path("a", "c") # => {3, ["a", "b", "c"]}

NOTE: Dijkstra assumes non-negative weights; negative edges are not supported.

Constructors

new

Source

Instance methods

add_edge(from : T, to : T, weight : W, directed : Bool = false) : Nil

Adds an edge from from to to with the given weight. Undirected by default (the reverse edge is added too); pass directed: true for a one-way edge. Re-adding an existing edge overwrites its weight.

Source

add_node(value : T) : Hash(T, W)

Registers value as a node if it is not already present, and returns its (possibly newly created) outgoing-edge map.

Source

adjacency

Source

dijkstra(source : T) : Hash(T, W)

Runs Dijkstra from source, returning the shortest distance to every reachable node (including source itself at distance zero). Unreachable nodes are simply absent from the result.

Source

empty?

Source

neighbors(value : T) : Hash(T, W)

Returns the outgoing edges of value as a {neighbor => weight} map, or an empty map if the node is absent.

Source

nodes

Source

shortest_path(source : T, target : T) : Tuple(W, Array(T)) | Nil

Returns the shortest path from source to target as {total_distance, [source, ..., target]}, or nil if target is unreachable (or either node is absent).

Source

size

Source

weight(from : T, to : T) : W | Nil

Returns the weight of the edge from from to to, or nil if there is no such edge.

Source