Hi *,
I have a question about the All Pair Shortest Path (Johnson) algorithm.
Here is my code:
#include
#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include
#include
#include
int main() {
using namespace boost;
typedef property >
VertexProperty;
typedef property >
EdgeProperty;
typedef property GraphProperty;
//adjacency_list
typedef adjacency_list Graph;
boost::graph_traits<Graph>::vertex_descriptor u, v, w, first, second;
int N = 10;
Graph g;
first = add_vertex(g);
put(vertex_index, g, first, num_vertices(g));
second = add_vertex(g);
put(vertex_index, g, second, num_vertices(g));
add_edge(first, second, g);
u = first;
v = second;
for (int i = 2; i < N; i++) {
w = add_vertex(g);
put(vertex_index, g, w, i + 1);
add_edge(u, w, g);
add_edge(v, w, g);
u = v;
v = w;
}
add_edge(u, first, g);
add_edge(v, second, g), add_edge(v, first, g);
std::cout << "Finished to build Graph" << std::endl;
//set weights to 1
typedef graph_traits<Graph>::edge_iterator EdgeIterator;
EdgeIterator ei, edge_end;
for ( boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei){
put(edge_weight, g, *ei, 1);
}
std::vector<int> d(N, (std::numeric_limits<int>::max)());
int D[N][N];
johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0]));
std::cout << " ";
for (int k = 0; k < N; ++k)
std::cout << std::setw(5) << k;
std::cout << std::endl;
for (int i = 0; i < N; ++i) {
std::cout << i << " -> ";
for (int j = 0; j < N; ++j) {
if (D[i][j] > 20 || D[i][j] < -20)
std::cout << std::setw(5) << "inf";
else
std::cout << std::setw(5) << D[i][j];
}
std::cout << std::endl;
}
return 0;
}
When I compile I get the error:
../src/BGLTest.cpp: In function 'int main()':
../src/BGLTest.cpp:73: error: no matching function for call to
'johnson_all_pairs_shortest_paths(main()::Graph&, int [(((long
unsigned int)(((int)N) - 1)) + 1u)][(((long unsigned int)(((int)N) -
1)) + 1u)], boost::bgl_named_params)'
What does that mean? I want to use the Johnson algorithm with a listS
= Vertexlist and listS = Egelist. With listS, vecS as in your
example it works fine. What can I do?
Thanks in advance,
Nico
