Single-Source Shorest Path

Performs a single-source shortest path query on the input graph, storing the shortest path distance and parent on each reachable vertex. All vertices will be initialized with their distance as infinity (MAX) and their active state as false, except the source-vertex, which will have its distance set to zero (0) and active state set to true. Parents of each vertex will be initialized to the vertex's descriptor.

Note, if the graph is unweighted, a breadth-first search may be a more suitable computation.

Parameters

size_t sssp(G g, Descriptor source, size_t k)
  • g: The graph_view over the input graph.
  • source: The descriptor of the source vertex for this traversal.
  • k: The maximum amount of asynchrony allowed in each phase. 0 <= k <= inf. k == 0 implies level-sync SSSP. k >= D implies fully asynchronous (D is diameter of graph).

Returns

The number of iterations performed by the paradigm.

Usage Example

auto graph =
  stapl::load_weighted_edge_list<stapl::properties::sssp_property, int>(argv[1]);

std::size_t iters = stapl::sssp(graph, 0, 10);

int dist = graph[10].property().distance();

std::cout << "vertex 10 is distance " << dist << "  away from vertex 0";

results matching ""

    No results matching ""