Types
ImplicitDijkstraAdjacent[T] = proc (v: T): seq[(T, int)] {.closure.}
- Source Edit
ImplicitDijkstraFinish[T] = proc (v: T): bool {.closure.}
- Source Edit
Procs
proc implicit_dijkstra[T](start: T; adjacent: ImplicitDijkstraAdjacent[T]): Table[ T, int]
- 始点から到達可能な各頂点までの最短距離を返す。 到達不能な頂点は返り値の Table に含まれない。 Source Edit
proc implicit_dijkstra_until[T](start: T; adjacent: ImplicitDijkstraAdjacent[T]; finish: ImplicitDijkstraFinish[T]; INF: int = INF64): int
- 非負辺を仮定し、最短距離が確定した頂点が初めて finish を 満たしたとき、その頂点までのコストを返す。 Source Edit
proc restore_implicit_dijkstra[T](start: T; adjacent: ImplicitDijkstraAdjacent[T]): tuple[ costs: Table[T, int], prev: Table[T, T]]
- adjacent(v) で辺を列挙する、頂点集合を明示しないグラフ上の Dijkstra 法。非負辺を仮定し、到達可能な頂点をすべて探索する。 Source Edit
proc shortest_path_implicit_dijkstra[T](start, goal: T; adjacent: ImplicitDijkstraAdjacent[T]; INF: int = INF64): tuple[path: seq[T], cost: int]
- 非負辺を仮定し、goal の最短距離が確定した時点で探索を終了する。 Source Edit