| Example Program Dijkstras Algorithm Computing single source shortest paths using Dijkstra algorithm. A tutorial about the dijkstra's algorithm, once using an external map and once using an internal map.
1 | #include <iostream>
| 2 | #include <seqan/graph_algorithms.h>
| 3 |
| 4 | using namespace seqan;
| 5 |
| 6 | int main() {
| 7 | typedef Graph<Directed<> > TGraph;
| 8 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
| 9 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
| 10 | typedef Size<TGraph>::Type TSize;
|
11 | TSize numEdges = 10;
| 12 | TVertexDescriptor edges[] = {0,1, 0,3, 1,2, 1,3, 2,4, 3,1, 3,2, 3,4, 4,0, 4,2};
| 13 | TGraph g;
| 14 | addEdges(g, edges, numEdges);
|
15 | unsigned int weights[] = {10, 5, 1, 2, 4, 3, 9, 2, 7, 6};
| 16 | String<unsigned int> weightMap;
| 17 | assignEdgeMap(g,weightMap, weights);
|
18 | String<unsigned int> predMap;
| 19 | String<unsigned int> distMap;
|
20 | dijkstra(g,0,weightMap,predMap,distMap);
|
21 | std::cout << "Single-Source Shortest Paths: " << std::endl;
| 22 | typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
| 23 | TVertexIterator it(g);
| 24 | while(!atEnd(it)) {
| 25 | std::cout << "Path from 0 to " << getValue(it) << ": ";
| 26 | _printPath(g,predMap,(TVertexDescriptor) 0, getValue(it));
| 27 | std::cout << " (Distance: " << getProperty(distMap, getValue(it)) << ")" << std::endl;
| 28 | goNext(it);
| 29 | }
|
30 | typedef unsigned int TEdgeCargo;
| 31 | typedef Directed<TEdgeCargo> TEdges;
| 32 | typedef Graph<TEdges> TCargoGraph;
|
33 | TCargoGraph cargo_g;
| 34 | addEdges(cargo_g, edges, numEdges);
|
35 | InternalMap<TEdgeCargo> intMap;
| 36 | assignEdgeMap(cargo_g, intMap, weights);
|
37 | clear(predMap);
| 38 | clear(distMap);
|
39 | dijkstra(cargo_g,0,intMap,predMap,distMap);
|
40 | std::cout << "Single-Source Shortest Paths: " << std::endl;
| 41 | typedef Iterator<TCargoGraph, VertexIterator>::Type TCargoVertexIterator;
| 42 | TCargoVertexIterator itC(cargo_g);
| 43 | while(!atEnd(itC)) {
| 44 | std::cout << "Path from 0 to " << getValue(itC) << ": ";
| 45 | _printPath(cargo_g,predMap,(TVertexDescriptor) 0, getValue(itC));
| 46 | std::cout << " (Distance: " << getProperty(distMap, getValue(itC)) << ")" << std::endl;
| 47 | goNext(itC);
| 48 | }
| 49 | return 0;
| 50 | }
|
|