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

Shortest Path Algorithms

Generic Algorithms for SSSP

Dijkstra's Algorithm for SSSP

Number Types

Graphs and Related Data Types

Graph Algorithms

Manual Entries: