|
|
Posted on 2009-04-09 19:16 lzmagic 阅读(2290) 评论(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不一样
你只要开个数组 记录每个顶点的入队次数, 如果哪个顶点入队次数超过顶点个数 那么有负循环.
|