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
|