Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Dijkstra's Algorithm for SSSP > Example DIJKSTRA_T()

## Example of How to Use `DIJKSTRA_T()`

The following program shows how the function `DIJKSTRA_T()` can be used to compute single source shortest paths in a directed graph with non-negative edge costs.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

In order to use the template function `DIJKSTRA_T()` we need to include `<LEDA/templates/shortest_path.t>`. We use the LEDA number type `integer` as the number type `NT` for the edge costs. In constrast to the C++ number type `int`, LEDA's `integer` does not overflow.

```#include <LEDA/graph/graph.h>
#include <LEDA/graph/templates/shortest_path.th>
#include <LEDA/numbers/integer.h>

using namespace leda;
```

In `main()` we first create a simple `graph G` with four nodes and six edges. We use an ```edge_array<integer> cost``` to store the costs of the edges of `G`.

```int main()
{
graph G;

node n0=G.new_node(); node n1=G.new_node();
node n2=G.new_node(); node n3=G.new_node();

edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n2);
edge e2=G.new_edge(n1,n2); edge e3=G.new_edge(n1,n3);
edge e4=G.new_edge(n2,n3); edge e5=G.new_edge(n3,n1);

edge_array<integer> cost(G);
cost[e0]=1; cost[e1]=2; cost[e2]=3;
cost[e3]=4; cost[e4]=5; cost[e5]=6;```

The ```node_array<edge> pred``` and the `node_array<integer> dist` are used for the result of `DIJKSTRA_T()`. `pred[v]` will contain the last edge on a shortest path from the source node `s` to `v`. This allows a construction of the complete shortest path. `dist[v]` will contain the length of a shortest path from `s` to `v`.

```
node_array<edge> pred(G);
node_array<integer> dist(G);
DIJKSTRA_T(G,n0,cost,dist,pred);

node v;
forall_nodes(v,G) {
G.print_node(v);
if (v==n0)
std::cout << " was source node." << std::endl;
else
if (pred[v]==nil)
std::cout << " is unreachable." << std::endl;
else {
std::cout << " " << dist[v] << " ";
G.print_edge(pred[v]);
std::cout << std::endl;
}
}

return 0;
}```

Dijkstra's Algorithm for SSSP

Integer

Graphs

Parameterized Graphs

Edge Arrays

Node Arrays

Checking the Results of an SSSP Algorithm

Manual Entries: