BellmanFord算法到SPFA算法

引用链接http://www.cnblogs.com/north_dragon/archive/2010/05/30/1747697.html
　　　　http://www.cnblogs.com/AbandonZHANG/archive/2012/07/26/2610833.html
  1 #include <iostream>
  2 #include <string>
  3 #include <vector>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <map>
  7 #include <algorithm>
  8 #include <list>
  9 #include <ctime>
 10 #include <set>
 11 #include <string.h>
 12 #include <queue>
 13 using namespace std;
 14 
 15 int maxData = 0x3fffffff;
 16 
 17 bool relax(int u, int v, int w) {
 18     if (v > u + w) {
 19         v = u + w;
 20         return true;
 21     } else
 22         return false;
 23 }
 24 
 25 bool bellman_ford(int s, vector<int> &d, vector<vector<int> > path) {
 26     int n = d.size();
 27     int i, j, k;
 28     bool judge;
 29     for (i = 0; i < n; ++i) {
 30         d[i] = maxData; //将除源点以外的其余点的距离设置为无穷大
 31     }
 32     d[s] = 0;
 33     for (i = 0; i < n - 1; i++) {
 34         for (j = 0; j < n; j++) {
 35             for (k = 0; k < n; k++) {
 36                 judge = relax(d[j], d[k], path[j][k]);
 37                 if (judge) {
 38                     d[k] = d[j] + path[j][k];
 39                 }
 40 
 41             }
 42         }
 43     }
 44 
 45     for (j = 0; j < n; j++) {
 46         for (k = 0; k < n; k++) {
 47             judge = relax(d[j], d[k], path[j][k]);
 48             if (judge) {
 49                 return true;
 50             }
 51 
 52         }
 53     }
 54 
 55     return false;
 56 }
 57 
 58 bool SPFA(int s, vector<int> &d, vector<vector<int> > path) {
 59     int n = d.size();
 60     queue<int> myqueue;
 61     int i;
 62 
 63     for (i = 0; i < n; ++i) {
 64         d[i] = maxData; //将除源点以外的其余点的距离设置为无穷大
 65     }
 66     vector<bool> final(n, false); //记录顶点是否在队列中，SPFA算法可以入队列多次
 67     vector<int> cnt(n, 0); //记录顶点入队列次数
 68     d[s] = 0; //源点的距离为0
 69     final[s] = true;
 70     cnt[s]++; //源点的入队列次数增加
 71     myqueue.push(s);
 72     int topint;
 73     while (!myqueue.empty()) {
 74         topint = myqueue.front();
 75         myqueue.pop();
 76         final[topint] = false;
 77         for (i = 0; i < n; ++i) {
 78             if (d[topint] < maxData && d[i] > d[topint] + path[topint][i]) {
 79                 d[i] = d[topint] + path[topint][i];
 80                 if (!final[i]) { //判断是否在当前的队列中
 81                     final[i] = true;
 82                     cnt[i]++;
 83                     if (cnt[i] >= n) //当一个点入队的次数>=n时就证明出现了负环。
 84                         return true;
 85                     myqueue.push(i);
 86                 }
 87             }
 88         }
 89     }
 90     return false;
 91 }
 92 
 93 int main() {
 94     vector<vector<int> > path(4, vector<int>(4, maxData));
 95     vector<int> d(4, maxData);
 96     bool judge;
 97     for (int i = 0; i < 4; i++)
 98         path[i][i] = 0;
 99     path[0][1] = path[1][0] = path[2][3] = 1;
100     path[1][2] = 5;
101     path[0][2] = 3;
102 
103     judge = SPFA(0, d, path);
104     if (!judge)
105         for (int i = 0; i < 4; i++)
106             cout << d[i] << endl;
107     else
108         cout << "存在负权回路\n";
109 
110     judge = bellman_ford(0, d, path);
111     if (!judge)
112         for (int i = 0; i < 4; i++)
113             cout << d[i] << endl;
114     else
115         cout << "存在负权回路\n";
116 
117     path[1][2] = 1;
118     path[2][0] = -3;
119     judge = SPFA(0, d, path);
120     if (!judge)
121         for (int i = 0; i < 4; i++)
122             cout << d[i] << endl;
123     else
124         cout << "存在负权回路\n";
125 
126     judge = bellman_ford(0, d, path);
127     if (!judge)
128         for (int i = 0; i < 4; i++)
129             cout << d[i] << endl;
130     else
131         cout << "存在负权回路\n";
132 
133     return 0;
134 
135 }