CGAL 6.1.1 - CGAL and the Boost Graph Library

Loading...
Searching...
No Matches
Functions
Graph Traversal
Reference Manual

##

Methods to traverse a graph, for example to find the shortest path between two vertices.

## Functions
template<typename Graph , typename OutputIterator , typename NamedParameters = parameters::Default_named_parameters>
OutputIterator | CGAL::dijkstra_shortest_path (const typename boost::graph_traits< Graph >::vertex_descriptor vs, const typename boost::graph_traits< Graph >::vertex_descriptor vt, const Graph &g, OutputIterator halfedge_sequence_oit, const NamedParameters &np=parameters::default_values())
| computes the shortest path between two vertices in a graph `g`, where the vertices must belong to the same connected component of `g`.

## Function Documentation

## ◆ dijkstra_shortest_path()

template<typename Graph , typename OutputIterator , typename NamedParameters = parameters::Default_named_parameters>

OutputIterator CGAL::dijkstra_shortest_path | ( | const typename boost::graph_traits< Graph >::vertex_descriptor | vs,
|  | const typename boost::graph_traits< Graph >::vertex_descriptor | vt,
|  | const Graph & | g,
|  | OutputIterator | halfedge_sequence_oit,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/boost/graph/dijkstra_shortest_path.h>`

computes the shortest path between two vertices in a graph `g`, where the vertices must belong to the same connected component of `g`.

Template Parameters

  Graph | a model of the concept `HalfedgeListGraph`
  OutputIterator | an output iterator with value type `boost::graph_traits<Graph>::halfedge_descriptor`
  NamedParameters | a sequence of Named Parameters

Parameters

  vs | source vertex
  vt | target vertex
  g | the graph
  halfedge_sequence_oit | the output iterator holding the output sequence of halfedges that form the shortest path from `vs` to `vt` on `g`
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating to each edge in the graph its weight or "length". The weights must all be non-negative. Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and a value type which as specified in the named parameter `distance_map`of the function `boost::graph::dijkstra_shortest_paths()`, with any model of `RingNumberType` fulfilling the requirements. Default: `get(boost::edge_weight, mesh)` |
  a property map associating to each vertex of `g` a unique index between `0` and `num_vertices(g) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

Examples
  BGL_surface_mesh/shortest_path.cpp.