graph dijkstra_shortest_paths metodu

named parameter kullanımı
Çıktılar predecessors ve distances vector'lerinde saklanır.

Örnek
Önce sonuçları saklamak için vector'ler oluşturulur.

std::vector<Vertex> predecessors(boost::num_vertices(graph)); // To store parents
std::vector<Weight> distances (boost::num_vertices(graph)); // To store distances

Bir map oluşturulur

IndexMap indexMap = boost::get(boost::vertex_index, graph);

vector'ler map'e verilir.

PredecessorMap predecessorMap(&predecessors[0],indexMap);
DistanceMap distanceMap      (&distances[0],   indexMap);

Başlangıç vertex ile çağrılır. Şöyle yaparız.

Vertex v0 = ...;

boost::dijkstra_shortest_paths(graph, v0, boost::distance_map(distanceMap).
  predecessor_map(predecessorMap));

Örnek graph + vertex + visitor + color_map + distance_map + predecessor_map + weight_map
Şöyle yaparız.

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

G g;
...
V start_vertex = ...;
V end_vertex   = ...;

size_t visited;
std::vector<boost::default_color_type>colors(num_vertices(g),boost::default_color_type{});
std::vector<V>                        _pred(num_vertices(g),   g.null_vertex());
std::vector<size_t>                   _dist(num_vertices(g),   -1ull);

my_visitor vis { end_vertex, visited };
auto predmap = _pred.data(); 
auto distmap = _dist.data(); 

boost::dijkstra_shortest_paths(g, start_vertex, 
  boost::visitor(vis).
  color_map(colors.data()).
  distance_map(distmap).
  predecessor_map(predmap).
  weight_map(boost::make_constant_property<E>(1ul))
);

Visitor şöyledir.

struct my_visitor : boost::default_dijkstra_visitor {
  using base = boost::default_dijkstra_visitor;
  struct done{};

  my_visitor(V vd, size_t& visited) : destination(vd), visited(visited) {}

  void finish_vertex(V v, G const& g) {
    ++visited;

    if (v == destination)
      throw done{};

      base::finish_vertex(v, g);
  }

private:
  V destination;
  size_t &visited;
};

Örnek - graph + vertex + predecessor_map + distance_map
Sonuçları saklamak için vector'ler oluşturulur.

vector<Graph::vertex_descriptor> p(num_vertices(g));
vector<uint32_t> distance (num_vertices(g));

Vector'lere map vermek için şöyle yaparız.

make_iterator_property_map(p.begin(), get(vertex_index, g));
make_iterator_property_map(d.begin(), get(vertex_index, g));

Başlangıç vertex hedef olabilir. Yani hedeften kaynağa doğru tersten ilerleyebiliriz. Şöyle yaparız.

const uint32_t to = ...;
Graph::vertex_descriptor v = vertex(to, g);

Şöyle yaparız.

dijkstra_shortest_paths(g, vertex(from, g),
  predecessor_map(make_iterator_property_map(p.begin(), get(vertex_index, g)))
  .distance_map(make_iterator_property_map(d.begin(), get(vertex_index, g))));

Hedeften kaynağa gittiğimiz için çıktyı dolaşmak için şöyle yaparız.

vector<Graph::edge_descriptor> path;
Graph::vertex_descriptor v = vertex(to, g);
...

for(auto u = p[v]; u != v; v = u, u = p[v])
{
  path.push_back(edge(u, v, g).first);
}

// Write shortest path
cout << "Distance: " << d[to] << endl;
for(auto i = path.rbegin() + 1; i != path.rend(); ++i)
{
  cout << source(*i, g) << " ";
}

Örnek - graph + vertex + predecessor_map + distance_map + weight_map
Graph şöyle.

0--(8)->1 --(20)-> 2 --(2)-> 3
 |            |                             ^
(18)      (7)                           |
------------------------------------ |

Sonuçları saklamak için vector oluştururuz.

std::vector<vertex_descriptor> predecessors(num_vertices(g));
std::vector<double>            distances(num_vertices(g));
    vertex_descriptor start = *(vertices(g).first);

Şöyle yaparız. weight olarak Edge nesnesinin getWeight() metodu kullanılır.

vertex_descriptor start = *(vertices(g).first);

auto v_index = get(boost::vertex_index, g);
auto weight = boost::make_transform_value_property_map(
std::mem_fn(&EdgeProperty::getWeight), get(boost::edge_bundle, g));

dijkstra_shortest_paths(
  g, start,
  predecessor_map(make_iterator_property_map(predecessors.begin(), v_index))
  .distance_map(make_iterator_property_map(distances.begin(), v_index))
  .weight_map(weight));

Sonucu görmek için şöyle yaparız.

std::cout << "distances and parents:\n";
for (auto v : boost::make_iterator_range(boost::vertices(g))) {
  auto id = g[v].getVertexID();
  std::cout << "distance(" << id << ") = " << distances[v] << ", ";
  std::cout << "parent(" << id << ") = " << g[predecessors[v]] << "\n";
}

Çıktı olarak şunu alırız.

distances and parents:
distance(0) = 0.000000, parent(0) = id 0 type LEVEL level 254 stair_id 254
distance(1) = 8.000000, parent(1) = id 0 type LEVEL level 254 stair_id 254
distance(2) = 17.000000, parent(2) = id 3 type STAIR level 254 stair_id 254
distance(3) = 15.000000, parent(3) = id 1 type STAIR level 254 stair_id 254

0'dan 1'e gitmek için 0->1 yolu izlenir, mesafe 8'dir.
0'dan 2'ye gitmek için 0->1->3->2 yolu izlenir, mesafe 17'dir.
0'dan 3'e gitmek içn 0->1->3 yolu izlenir, mesafe 15'tir.

Örnek - graph + vertex + predecessor_map + distance_map + sabit weight
Açıklaması şöyle

Use the Bellman-Ford algorithm for the case when some edge weights are negative. Use breadth-first search instead of Dijkstra's algorithm when all edge weights are equal to one.

Şöyle yaparız. Weight olarak sabit bir değere veriliyor.

Graph g;

std::vector<VertexDesc> pr(num_vertices(gc.graph));
std::vector<int> d(num_vertices(gc.graph));

auto v_index = get(boost::vertex_index, g); 

dijkstra_shortest_paths(g, vGoal,
  boost::predecessor_map(boost::make_iterator_property_map(pr.begin(), v_index))
    .distance_map(boost::make_iterator_property_map(d.begin(), v_index))
    .weight_map(boost::make_constant_property<EdgeDesc>(1.0))
);