Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Checking the Results of an SSSP Algorithm

Checking the Results of an SSSP Algorithm

Let G be a directed graph, s a node of G, and cost a cost function on the edges of G. Edge costs may be positive or negative. A single source shortest path algorithm computes the shortest paths from s to all other nodes of G with respect to the cost.

CHECK_SP_T() checks whether the result of the single source shortest paths computation is a correct solution of the SSSP problem (G,s,cost). CHECK_SP_T() is a template function. The template parameter NT is determined by the number type used for the shortest path computation.

Example of How to Use CHECK_SP_T()

CHECK_SP() is the name of the preinstantiated versions of CHECK_SP_T(). There is one function CHECK_SP() for edge costs of type int and one for double.

Example of How to Use CHECK_SP()

Running time

The running time of CHECK_SP_T() and CHECK_SP() for a graph G=(V,E) is linear in the size of the graph (O(|V|+|E|)).

Tips

Checking the result is much easier than computing a solution of a single source shortest path problem. Therefore, the checking functions are less complicated and less error prone. Moreover, checking is only linear in the size of the graph. So the overhead is quite small. Use CHECK_SP_T() or CHECK_SP() to ensure the correctness of your result

  • if you can afford the overhead
  • if there are negative cost cycles and you want more details about the result

See also:

Shortest Path Algorithms

Generic Algorithms for SSSP

SSSP Algorithm for Acyclic Graphs

Dijkstra's Algorithm for SSSP

Bellman-Ford Algorithm for SSSP


Number Types

Graphs and Related Data Types

Graph Algorithms


Manual Entries:

Manual Page Shortest Path Algorithms




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH