lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

Bellman_Ford算法 SPFA算法

Posted on 2009-04-09 19:16 lzmagic 阅读(2217) 评论(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(37));
    g[
1].push_back(Edge(2,  5)); g[1].push_back(Edge(38)); 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(49));
    g[
4].push_back(Edge(0,  2)); g[4].push_back(Edge(27));
    
    
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(37));
    g[
1].push_back(Edge(2,  5)); g[1].push_back(Edge(38)); 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(49));
    g[
4].push_back(Edge(0,  2)); g[4].push_back(Edge(27));
    
    
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 dustman
其实你这个SPFA 写错了, 就是判断不了负循环 不信你可以试下,他判断负循环的方法跟BELLMAN不一样

你只要开个数组 记录每个顶点的入队次数, 如果哪个顶点入队次数超过顶点个数 那么有负循环.

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理