21.boost Ford最短路径算法(效率低)

到某个节点最近距离                  最短路径当前节点的父节点

完整代码

 #include <iostream>

 #include <string>

 #include <utility>

 #include <vector>

 #include <deque>

 #include <boost/graph/adjacency_list.hpp>

 //A*寻路算法

 #include <boost\graph\astar_search.hpp>

 //dijsktra

 #include <boost\graph\dijkstra_shortest_paths.hpp>

 //bellman-Ford算法

 #include <boost\graph\bellman_ford_shortest_paths.hpp>

 using namespace std;

 using namespace boost;

 void main()

 {

     //定义节点和边的相关对象和属性

     enum { u, v, x, y, z, N };

     char name[] = { 'u', 'v', 'x', 'y', 'z' };

     typedef std::pair < int, int >E;

     E edge_array[] = { E(u, y), E(u, x), E(u, v), E(v, u),

         E(x, y), E(x, v), E(y, v), E(y, z), E(z, u), E(z, x) };

     int weights[] = { -, , , -, , -, , , ,  };

     int num_arcs = sizeof(edge_array) / sizeof(E);

     //定义所用的图种类和相关类型

     typedef adjacency_list < vecS, vecS, directedS,

         no_property, property < edge_weight_t, int > > Graph;

     //生成图对象

     Graph g(edge_array, edge_array + num_arcs, weights, N);

     graph_traits < Graph >::edge_iterator ei, ei_end;

     //distance用于放置依近到远的路径距离

     std::vector<int> distance(N, (std::numeric_limits < short >::max)());

     //parent用于放置最短路径生成树的各个顶点的父节点

     std::vector<std::size_t> parent(N);

     for (int i = ; i < N; ++i)

         parent[i] = i;

     //将源点z对应距离设为0

     distance[z] = ;

     //应用Bellman-Ford算法

     bool r = bellman_ford_shortest_paths

     (g, int(N), weight_map(get(edge_weight, g)).distance_map(&distance[]).

         predecessor_map(&parent[]));

     if (r)

     {

         std::cout << "源点z到各点的最短路径\n";

         std::cout << "目的点\t" << "最短路径\t" << "最短路径树的父节点:\n";

         for (int i = ; i < N; ++i)

             std::cout << name[i] << ": \t" << distance[i]

             << "\t\t" << name[parent[i]] << std::endl;

     }

     else

         std::cout << "negative cycle" << std::endl;

     system("pause");

 }