最常用的五大算法

分治法应用场景：

1. /* 主题：单源最短路径问题 
2. * 作者：chinazhangjie 
3. * 邮箱：chinajiezhang@gmail.com 
4. * 开发语言：C++ 
5. * 开发环境：Mircosoft Virsual Studio 2008 
6. * 时间: 2010.11.01 
7. */  
8.   
9. #include <iostream>  
10. #include <vector>  
11. #include <queue>  
12. #include <limits>  
13. using namespace std;  
14.   
15. struct node_info  
16. {  
17. public:  
18.     node_info (int i,int w)   
19.         : index (i), weight (w) {}  
20.     node_info ()   
21.         : index(0),weight(0) {}  
22.     node_info (const node_info & ni)   
23.         : index (ni.index), weight (ni.weight) {}  
24.   
25.     friend   
26.     bool operator < (const node_info& lth,const node_info& rth) {  
27.         return lth.weight > rth.weight ; // 为了实现从小到大的顺序  
28.     }  
29.   
30. public:  
31.     int index; // 结点位置  
32.     int weight; // 权值  
33. };  
34.   
35. struct path_info   
36. {  
37. public:  
38.     path_info ()  
39.         : front_index(0), weight (numeric_limits<int>::max()) {}  
40.   
41. public:  
42.     int front_index;  
43.     int weight;  
44. };  
45.   
46. // single source shortest paths  
47. class ss_shortest_paths  
48. {  
49.        
50. public:  
51.     ss_shortest_paths (const vector<vector<int> >& g,int end_location)   
52.         :no_edge (-1), end_node (end_location), node_count (g.size()) , graph (g)   
53.     {}  
54.   
55.     // 打印最短路径  
56.     void print_spaths () const {  
57.         cout << "min weight : " << shortest_path << endl;  
58.         cout << "path: " ;  
59.         copy (s_path_index.rbegin(),s_path_index.rend(),  
60.             ostream_iterator<int> (cout, " "));  
61.         cout << endl;  
62.     }  
63.   
64.     // 求最短路径  
65.     void shortest_paths () {  
66.         vector<path_info> path(node_count);  
67.         priority_queue<node_info,vector<node_info> > min_heap;  
68.         min_heap.push (node_info(0,0));    // 将起始结点入队  
69.   
70.         while (true) {  
71.             node_info top = min_heap.top ();    // 取出最大值  
72.             min_heap.pop ();  
73.   
74.             // 已到达目的结点  
75.             if (top.index == end_node) {  
76.                 break ;  
77.             }  
78.             // 未到达则遍历  
79.             for (int i = 0; i < node_count; ++ i) {  
80.                 // 顶点top.index和i间有边，且此路径长小于原先从原点到i的路径长   
81.                 if (graph[top.index][i] != no_edge &&   
82.                     (top.weight + graph[top.index][i]) < path[i].weight) {  
83.                     min_heap.push (node_info (i,top.weight + graph[top.index][i]));  
84.                     path[i].front_index = top.index;  
85.                     path[i].weight = top.weight + graph[top.index][i];  
86.                 }  
87.             }  
88.             if (min_heap.empty()) {  
89.                 break ;  
90.             }  
91.         }  
92.   
93.         shortest_path = path[end_node].weight;  
94.         int index = end_node;  
95.         s_path_index.push_back(index) ;  
96.         while (true) {  
97.             index = path[index].front_index ;  
98.             s_path_index.push_back(index);  
99.             if (index == 0) {  
100.                 break;  
101.             }  
102.         }  
103.     }  
104.   
105. private:  
106.     vector<vector<int> >    graph ;            // 图的数组表示  
107.     int                        node_count;        // 结点个数  
108.     const int                no_edge;        // 无通路  
109.     const int                end_node;        // 目的结点  
110.     vector<int>                s_path_index;    // 最短路径  
111.     int                        shortest_path;    // 最短路径  
112. };  
113.   
114. int main()  
115. {  
116.     const int size = 11;   
117.     vector<vector<int> > graph (size);  
118.     for (int i = 0;i < size; ++ i) {  
119.         graph[i].resize (size);  
120.     }  
121.     for (int i = 0;i < size; ++ i) {  
122.         for (int j = 0;j < size; ++ j) {  
123.             graph[i][j] = -1;  
124.         }  
125.     }  
126.     graph[0][1] = 2;  
127.     graph[0][2] = 3;  
128.     graph[0][3] = 4;  
129.     graph[1][2] = 3;  
130.     graph[1][5] = 2;  
131.     graph[1][4] = 7;  
132.     graph[2][5] = 9;  
133.     graph[2][6] = 2;  
134.     graph[3][6] = 2;  
135.     graph[4][7] = 3;  
136.     graph[4][8] = 3;  
137.     graph[5][6] = 1;  
138.     graph[5][8] = 3;  
139.     graph[6][9] = 1;  
140.     graph[6][8] = 5;  
141.     graph[7][10] = 3;  
142.     graph[8][10] = 2;  
143.     graph[9][8] = 2;  
144.     graph[9][10] = 2;  
145.   
146.     ss_shortest_paths ssp (graph, 10);  
147.     ssp.shortest_paths ();  
148.     ssp.print_spaths ();  
149.     return 0;  
150. }