| Example Program Floyd-Warshall Algorithm Computing all-pairs shortest paths using Floyd-Warshall algorithm. A tutorial about the Floyd-Warshall algorithm.
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 = 9;
| 12 | TVertexDescriptor edges[] = {0,1, 0,2, 0,4, 1,3, 1,4, 2,1, 3,0, 3,2, 4,3};
| 13 | TGraph g;
| 14 | addEdges(g,edges, numEdges);
| 15 | ::std::cout << g << ::std::endl;
|
16 | int weights[] = {3, 8, -4, 1, 7, 4, 2, -5, 6};
| 17 | String<int> weightMap;
| 18 | resizeEdgeMap(g,weightMap, weights);
|
19 | String<int> distMat;
| 20 | String<TVertexDescriptor> predMat;
|
21 | floyd_warshall(g,weightMap, distMat, predMat);
|
22 | unsigned int len = (unsigned int) std::sqrt((double) length(distMat));
| 23 | for (TSize row=0;row < len;++row) {
| 24 | for (TSize col=0;col < len;++col) {
| 25 | ::std::cout << row << "," << col << " (Distance=" << getValue(distMat, row*len + col) << "): ";
| 26 | _print_all_pairs_shortest_path(g,predMat,row,col);
| 27 | ::std::cout << ::std::endl;
| 28 | }
| 29 | }
| 30 | return 0;
| 31 | }
|
|