shortest_path

関数 · 単一始点最短路 (shortest_path)

// (1)
template <template <class...> class Heap = dijkstra_priority_queue, properly_weighted_graph_type G, class T = graph_weight_t<G>>
std::vector<T> shortest_path(const G &g, int s = 0, T inf = std::numeric_limits<T>::max());

// (2)
template <unweighted_graph_type G>
std::vector<int> shortest_path(const G &g, int s = 0, int inf = std::numeric_limits<int>::max());

概要

(1) 単一始点最短路（実重み付きグラフはダイクストラ法）

• テンプレートパラメータ Heap: 使用するヒープ。既定は std::priority_queue ベースの最小ヒープ。 binary_heap / fibonacci_heap を渡すと decrease-key 方式に切り替わる。 いずれも Heap<Key, Value, Comp>（Key=順序基準, Value=付随データ）形式で push(key, value) / top() -> pair<key, value> / pop / empty を持つこと。
• テンプレートパラメータ G: 実重み付きグラフ型（list_graph<T> / csr_graph<T>、T は非 void）
• 計算量: 二分ヒープでは $O((V+E)\log V)$
• 備考: 重みなしグラフ（*_graph<void>）は下の BFS 版が選ばれる。
• 備考: update を持つヒープでは頂点ごとにハンドルを保持して decrease-key し、 ヒープ内要素を高々 V 個に保つ。持たないヒープでは緩和のたびに push して 取り出し時に stale をスキップする lazy-deletion 方式になる。

(2) 単一始点最短路（重みなしグラフは BFS で $O(V+E)$）

• テンプレートパラメータ G: 重みなしグラフ型（list_graph<void> / csr_graph<void> のいずれでも可）
• 計算量: $O(V+E)$
• 備考: 重みが $1$ 固定なので priority_queue 不要。unweighted_graph_type と properly_weighted_graph_type は排他なので、重みなしグラフではこちらが選ばれる。

関連項目

• dijkstra_priority_queue — shortest_path の既定ヒープ（std::priority_queue ベースの最小ヒープ）
• decrease_key_heap — decrease-key（update）を持つヒープか
• shortest_path_negative — 単一始点最短路（負辺ありはベルマンフォード法）
• shortest_path_spfa — 単一始点最短路（負辺ありは SPFA）