1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edge_list.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>
using namespace::boost;
using namespace::std;
struct EdgeProperties {
int weight;
};
enum { A, B, C, D, E, F, G, H, I, J, N };
char name[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };
typedef adjacency_list < vecS, vecS, directedS, no_property, EdgeProperties> Graph;
vector <int> depart;
vector <int> cible;
struct MyBellmanVisitor : public bellman_visitor<>
{
template <typename Edge, typename Graph>
void examine_edge(Edge e, Graph& g) const
{
if (name[source(e,g)]=='H' || name[target(e,g)]=='H'){
depart.push_back(source(e,g));
cible.push_back(target(e,g));
remove_edge(e,g);
}
}
};
void bfv(Graph g, property_map<Graph, int EdgeProperties::*>::type weight_pmap,vector<int> distance, vector<size_t> parent){
cout<<"\n RESOLUTION DU PLUS COURT CHEMIN AVEC BELLMAN FORD VISITOR"<<endl;
bool r = bellman_ford_shortest_paths
(g, int (N), weight_map(weight_pmap).distance_map(&distance[0]).
predecessor_map(&parent[0]).visitor(MyBellmanVisitor()));
if (r){
for (int i = 0; i < N; ++i){
std::cout << "distance(" << name[i] << ") = " << distance[i] << ", ";
std::cout << "parent(" << name[i] << ") = " << name[parent[i]] << std::endl;
}
}
}
void bf(Graph g, property_map<Graph, int EdgeProperties::*>::type weight_pmap,vector<int> distance, vector<size_t> parent){
cout<<"\n RESOLUTION DU PLUS COURT CHEMIN AVEC BELLMAN FORD CLASSIQUE"<<endl;
bool r = bellman_ford_shortest_paths
(g, int (N), weight_map(weight_pmap).distance_map(&distance[0]).
predecessor_map(&parent[0]));
if (r){
for (int i = 0; i < N; ++i){
std::cout << "distance(" << name[i] << ") = " << distance[i] << ", ";
std::cout << "parent(" << name[i] << ") = " << name[parent[i]] << std::endl;
}
}
}
int main() {
typedef std::pair < int, int >Ed;
const int n_edges = 11;
Ed edge_array[] = { Ed(A,B), Ed(A,C), Ed(A,E), Ed(B,F),
Ed(C,G), Ed(C,H), Ed(D,H), Ed(E,J), Ed(F,I), Ed(H,J), Ed(I,J) };
int weight[n_edges] = { 85, 217, 173, 80, 186, 103, 183, 502, 250, 167, 84};
Graph g(edge_array, edge_array + n_edges, N);
property_map<Graph, int EdgeProperties::*>::type weight_pmap;
weight_pmap = get(&EdgeProperties::weight, g);
std::vector<int> distance(N, (std::numeric_limits < short >::max)());
std::vector<std::size_t> parent(N);
int i = 0;
graph_traits < Graph >::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei, ++i) {weight_pmap[*ei] = weight[i];}
for (i = 0; i < N; ++i) {parent[i] = i;}
distance[A] = 0;
bfv(g,weight_pmap,distance,parent);
bf(g,weight_pmap,distance,parent);
return EXIT_SUCCESS;
} |
