# `johnson_all_pairs_shortest_paths`

    // 名前付きパラメータバージョン
    template <typename Graph, typename DistanceMatrix, typename P, typename T, typename R>
    bool johnson_all_pairs_shortest_paths(Graph& g, DistanceMatrix& D,
      const bgl_named_params<P, T, R>& params = all defaults)

    // 名前無しパラメータバージョン
    template <typename Graph, typename DistanceMatrix,
              typename VertexIndex, typename WeightMap, typename DT>
    bool
    johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1,
      DistanceMatrix& D,
      VertexIndex id1, Weight w1, DT zero)

このアルゴリズムはグラフ中の全ての頂点のペア間の最短距離を発見する。 アルゴリズムはもしグラフ中に負の重みの閉路が存在する場合は false を返し、 そうでなければ true を返す。各頂点のペア間の距離は距離行列 `D`に しまわれる。これは O(V E log V) の時間複雑性を持つ持つより徹底的な時間がかかるグラフ・アルゴリズムの一つである。

### Where Defined

`boost/graph/johnson_all_pairs_shortest.hpp`

### Parameters

IN: `Graph& g`

> 有向グラフまたは無向グラフ。グラフの型は Vertex List Graph、Edge List Graph、そして Incidence Graph のモデルでなければならない。

OUT: `DistanceMatrix& D`

> グラフ中の各頂点 u,v のペア間の最短経路の長さは `D[u][v]` 中にしまわれる。型が {`DistanceMatrix, vertex_descriptor, D`} の 集合は `D` が `DistanceMap` の値型である BasicMatrix のモデルでなければならない。

### Named Parameters

IN: `weight_map(WeightMap w_map)`

> グラフ中の各辺の重みまたは“長さ”。`WeightMap` の型は Readable Property Map のモデルでなければならない。グラフの辺記述子型は重みマップのキー型と して使用できる必要がある。マップの値型は距離マップの値型を伴った Addable でなければならない。
> デフォルト: `get(edge_weight, g)`

UTIL: `weight_map2(WeightMap2 w2_map)`

> このパラメータはもはや必要とされず、無視されるだろう。

IN: `vertex_index_map(VertexIndexMap i_map)`

> これは各頂点を `[0, num_vertices(g))` の範囲において整数にマップする。 これは Dijkstra のアルゴリズムの内部の呼び出し中に、ヒープ・データ構造を効率 よく更新するのに必要である。`VertexIndexMap` は Readable Property Map のモデルでなければならない。マップの値型は汎整数型でなければならない。 グラフの頂点記述子型はマップのキー型として使用できる必要がある。
> デフォルト: `get(vertex_index, g)`

UTIL: `distance_map(DistanceMap d_map)`

> このパラメータはもはや必要とされず、無視されるだろう。

IN: `distance_compare(CompareFunction cmp)`

> この関数はどの頂点が始点により近いか決定するために距離を比較するのに使われる。 `CompareFunction` の型は Binary Predicate のモデルでなければならず、`DistanceMap` プロパティ・ マップの値型に一致する引数型を持たなければならない。
> デフォルト: `std::less<DT>` ここに `DT=typename property_traits<WeightMap>::value_type`

IN: `distance_combine(CombineFunction cmb)`

> この関数は道の距離を計算するために、距離を結合するのに使われる。 `CombineFunction` の型は Binary Function のモデルでなければならない。二項関数の第一引数の型は `DistanceMap` プロパティ・マップの値型に一致していなければならず、 第二引数の型は `WeightMap` プロパティ・マップの値型に一致していなければ ならない。結果型は距離の値型と同じでなければならない。
> デフォルト: `std::plus<DT>` ここに `DT=typename property_traits<WeightMap>::value_type`

IN: `distance_inf(DT inf)`

> この値はアルゴリズムの開始前に各頂点のための距離を初期化するのに使われる。 型 `DT` は `WeightMap` の値型でなければならない。
> デフォルト: `std::numeric_limits::max()`

IN: `distance_zero(DT zero)`

> この値はアルゴリズムの開始前に始点のための距離を初期化するのに使われる。 型 `DT` は `WeightMap` の値型でなければならない。
> デフォルト: `0`

UTIL/OUT: `color_map(ColorMap c_map)`

> これは頂点に印をつけるためにアルゴリズムの実行の間使われる。頂点は白色から 始めて、それがキュー中に挿入された時に灰色になる。それからそれがキューから 取り除かれた時に黒色になる。アルゴリズムの終了時に、始点から到達可能な頂点は 黒色に色づけされている。その他の全ての頂点は白色のままである。 `ColorMap` の型は Read/Write Property Map のモデルでなければならない。頂点記述子はマップのキー型として 使用できる必要があり、マップの値型は Color Value のモデルでなければならない。
> デフォルト: `サイズ num_vertices(g)` の `default_color_type` の `std::vector` から作られた `iterator_property_map` で、添え字マップには `i_map` を用いる。

### Complexity

時間複雑性は O(V E log V) である。

### Example

ファイル `example/johnson-eg.cpp` は CLR [8] の 568ページからの例のグラフに 全てのペアの最短経路のための Johnson のアルゴリズムを適用している。

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)