|
|
Posted on 2009-04-09 19:16 lzmagic 閱讀(2312) 評論(1) 編輯 收藏 引用 所屬分類: Algorithm
  /**//**
 * BELLMAN_FORD (簡單版) 單源最短路徑算法（允許存在負邊）
* 輸入：(1)有向圖g；
* (2)源點s。
* 輸出：(1)源點s到各點的最短路徑長dist；
* (2)源點s到各點的最短路徑prev。
* 結構: 圖g用鄰接表表示
* 算法：Bellman_Ford算法
* 復雜度：O(|E|*|V|)
 */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
struct Edge
 {
int v, w;
  Edge(int vertex, int weight): v(vertex), w(weight) { }
};
int n; // n : 頂點數
vector<list<Edge> > g; // g : 圖(graph)(用鄰接表(adjacent list)表示)
int s; // s : 源點(source)
vector<int> dist; // dist : 源點s到各點的最短路徑長
vector<int> prev; // prev : 各點最短路徑的前一頂點
bool Bellman_Ford()
{
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化dist、prev。
dist[s] = 0; // 初始化源點s到自身的路徑長為0。
for (int i = 0; i < n - 1; ++i) // 迭代(n - 1)次。(因為無回路的路徑步數最多(n -1)次)
for (int u = 0; u < n; ++u)
for (list<Edge>::iterator it = g[u].begin(); it != g[u].end(); ++it)// 遍歷每條邊，
if (dist[it->v] > dist[u] + it->w) // 如果dist[u] + weight[u][v] < dist[v]，
{
dist[it->v] = dist[u] + it->w;
prev[it->v] = u; // 調整各點的最短路徑長dist和最短路徑的前一頂點 prev。
 }
for (int u = 0; u < n; ++u)
for (list<Edge>::iterator it = g[u].begin(); it != g[u].end(); ++it) // 遍歷每條邊，
if (dist[it->v] > dist[u] + it->w) // 如果dist[u] + weight[u][v] < dist[v]，
return false; // 說明存在負值回路，失敗；
return true; // 否則成功。
}
void Print_SP(int v)
{
if (v != s) Print_SP(prev[v]);
cout << v << " ";
}
int main()
{
n = 5;
g.assign(n, list<Edge>());
g[0].push_back(Edge(1, 6)); g[0].push_back(Edge(3, 7));
g[1].push_back(Edge(2, 5)); g[1].push_back(Edge(3, 8)); g[1].push_back(Edge(4, -4));
g[2].push_back(Edge(1, -2));
g[3].push_back(Edge(2, -3)); g[3].push_back(Edge(4, 9));
g[4].push_back(Edge(0, 2)); g[4].push_back(Edge(2, 7));
if (Bellman_Ford())
{
copy(dist.begin(), dist.end(), ostream_iterator<int>(cout, " ")); cout << endl;
for (int i = 0; i < n; ++i)
if (dist[i] != INT_MAX)
{
cout << s << "->" << i << ": ";
Print_SP(i);
cout << endl;
}
}
else
{
cout << "Graph contains a negative-weight cycle" << endl;
}
system("pause");
return 0;
}
/**//**
* SPFA (Shortest Path Faster Algorithm)
* BELLMAN_FORD (升級版) 單源最短路徑算法（允許存在負邊）
* 輸入：(1)有向圖g；
* (2)源點s。
* 輸出：(1)源點s到各點的最短路徑長dist；
* (2)源點s到各點的最短路徑prev。
* 結構: 圖g用鄰接表表示
* 算法：SPFA算法
* 復雜度：O(|E|*|V|)
*/
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
struct Edge
{
int v, w;
Edge(int vertex, int weight): v(vertex), w(weight) { }
};
int n; // n : 頂點數
vector<list<Edge> > g; // g : 圖(graph)(用鄰接表(adjacent list)表示)
int s; // s : 源點(source)
vector<int> dist; // dist : 源點s到各點的最短路徑長
vector<int> prev; // prev : 各點最短路徑的前一頂點
bool SPFA()
{
queue<int> que;
vector<bool> pushed(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化pushed、dist、prev。
dist[s] = 0; que.push(s); pushed[s] = true; // 初始化源點s到自身的路徑長為0，入隊。
while (!que.empty()) // 如果隊列que非空，
{
int u = que.front(); que.pop(); pushed[u] = false; // 頂點u出隊，
for (list<Edge>::iterator it = g[u].begin(); it != g[u].end(); ++it) // 遍歷所有u指向的頂點v，
if (dist[it->v] > dist[u] + it->w) // 如果dist[u] + weight[u][v] < dist[v]，
{
dist[it->v] = dist[u] + it->w;
prev[it->v] = u; // 調整各點的最短路徑長dist和最短路徑的前一頂點 prev；
if (!pushed[it->v]) { que.push(it->v); pushed[it->v] = true; } // 如果頂點v不在隊列中，入隊。
}
}
for (int u = 0; u < n; ++u)
for (list<Edge>::iterator it = g[u].begin(); it != g[u].end(); ++it) // 遍歷每條邊，
if (dist[it->v] > dist[u] + it->w) // 如果dist[u] + weight[u][v] < dist[v]，
return false; // 說明存在負值回路，失敗；
return true; // 否則成功。
}
void Print_SP(int v)
{
if (v != s) Print_SP(prev[v]);
cout << v << " ";
}
int main()
{
n = 5;
g.assign(n, list<Edge>());
g[0].push_back(Edge(1, 6)); g[0].push_back(Edge(3, 7));
g[1].push_back(Edge(2, 5)); g[1].push_back(Edge(3, 8)); g[1].push_back(Edge(4, -4));
g[2].push_back(Edge(1, -2));
g[3].push_back(Edge(2, -3)); g[3].push_back(Edge(4, 9));
g[4].push_back(Edge(0, 2)); g[4].push_back(Edge(2, 7));
if (SPFA())
{
copy(dist.begin(), dist.end(), ostream_iterator<int>(cout, " ")); cout << endl;
for (int i = 0; i < n; ++i)
if (dist[i] != INT_MAX)
{
cout << s << "->" << i << ": ";
Print_SP(i);
cout << endl;
}
}
else
{
cout << "Graph contains a negative-weight cycle" << endl;
}
system("pause");
return 0;
}
Feedback
# re: Bellman_Ford算法 SPFA算法 回復 更多評論
2009-05-21 08:39 by
其實你這個SPFA 寫錯了, 就是判斷不了負循環 不信你可以試下,他判斷負循環的方法跟BELLMAN不一樣
你只要開個數組 記錄每個頂點的入隊次數, 如果哪個頂點入隊次數超過頂點個數 那么有負循環.
|