|
|
Posted on 2009-04-09 19:16 lzmagic 閱讀(2302) 評論(1) 編輯 收藏 引用 所屬分類: Algorithm
  /**//**
 * BELLMAN_FORD (簡單版) 單源最短路徑算法（允許存在負(fù)邊）
* 輸入：(1)有向圖g；
* (2)源點(diǎn)s。
* 輸出：(1)源點(diǎn)s到各點(diǎn)的最短路徑長dist；
* (2)源點(diǎn)s到各點(diǎn)的最短路徑prev。
* 結(jié)構(gòu): 圖g用鄰接表表示
* 算法：Bellman_Ford算法
* 復(fù)雜度：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 : 頂點(diǎn)數(shù)
vector<list<Edge> > g; // g : 圖(graph)(用鄰接表(adjacent list)表示)
int s; // s : 源點(diǎn)(source)
vector<int> dist; // dist : 源點(diǎn)s到各點(diǎn)的最短路徑長
vector<int> prev; // prev : 各點(diǎn)最短路徑的前一頂點(diǎn)
bool Bellman_Ford()
{
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化dist、prev。
dist[s] = 0; // 初始化源點(diǎn)s到自身的路徑長為0。
for (int i = 0; i < n - 1; ++i) // 迭代(n - 1)次。(因?yàn)闊o回路的路徑步數(shù)最多(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; // 調(diào)整各點(diǎn)的最短路徑長dist和最短路徑的前一頂點(diǎn) 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; // 說明存在負(fù)值回路，失敗；
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 (升級版) 單源最短路徑算法（允許存在負(fù)邊）
* 輸入：(1)有向圖g；
* (2)源點(diǎn)s。
* 輸出：(1)源點(diǎn)s到各點(diǎn)的最短路徑長dist；
* (2)源點(diǎn)s到各點(diǎn)的最短路徑prev。
* 結(jié)構(gòu): 圖g用鄰接表表示
* 算法：SPFA算法
* 復(fù)雜度：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 : 頂點(diǎn)數(shù)
vector<list<Edge> > g; // g : 圖(graph)(用鄰接表(adjacent list)表示)
int s; // s : 源點(diǎn)(source)
vector<int> dist; // dist : 源點(diǎn)s到各點(diǎn)的最短路徑長
vector<int> prev; // prev : 各點(diǎn)最短路徑的前一頂點(diǎn)
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; // 初始化源點(diǎn)s到自身的路徑長為0，入隊(duì)。
while (!que.empty()) // 如果隊(duì)列que非空，
{
int u = que.front(); que.pop(); pushed[u] = false; // 頂點(diǎn)u出隊(duì)，
for (list<Edge>::iterator it = g[u].begin(); it != g[u].end(); ++it) // 遍歷所有u指向的頂點(diǎn)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; // 調(diào)整各點(diǎn)的最短路徑長dist和最短路徑的前一頂點(diǎn) prev；
if (!pushed[it->v]) { que.push(it->v); pushed[it->v] = true; } // 如果頂點(diǎn)v不在隊(duì)列中，入隊(duì)。
}
}
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; // 說明存在負(fù)值回路，失敗；
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算法 回復(fù) 更多評論
2009-05-21 08:39 by
其實(shí)你這個(gè)SPFA 寫錯(cuò)了, 就是判斷不了負(fù)循環(huán) 不信你可以試下,他判斷負(fù)循環(huán)的方法跟BELLMAN不一樣
你只要開個(gè)數(shù)組 記錄每個(gè)頂點(diǎn)的入隊(duì)次數(shù), 如果哪個(gè)頂點(diǎn)入隊(duì)次數(shù)超過頂點(diǎn)個(gè)數(shù) 那么有負(fù)循環(huán).
|