lzm

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

USP 无权最短路径算法

Posted on 2009-04-09 10:44 lzmagic 阅读(2133) 评论(0)  编辑 收藏 引用 所属分类: Algorithm
/**
 * USP 无权最短路径算法(Unweighted Shortest Path Algorithm)
 * 输入：(1)图g；        // 有向图或者无向图 
 *         (2)源点s。 
 * 输出：(1)源点s到各点的无权最短路径长dist(路径的边数最小)； 
 *         (2)源点s到各点的无权最短路径prev。 
 * 结构: 图g用邻接表表示，最短路径长dist用数组表示。 
 * 算法：广度优先搜索(BFS)
 * 复杂度：O(|E|+|V|)~O(|E|)  
 */ 
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n;                        // n : 顶点个数 
vector<list<int> > g;        // g : 图(graph)(用邻接表(adjacent list)表示) 
int s;                        // s : 源点(source)
vector<int> dist;            // dist : 源点s到各点之间的距离
vector<int> prev;            // prev : 各点最短路径的前一顶点号 

void USP()        // 广度优先搜索(BFS)
{
    queue<int> que;
    dist.assign(n, INT_MAX);                     // 初始化dist， 
    prev.resize(n);                                // 初始化prev。 
    dist[s] = 0; que.push(s);                    // s到自身距离为0，s入队。 
    while (!que.empty())                         
    {
        int v = que.front(); que.pop();            // v出队， 
        for (list<int>::iterator it = g[v].begin(); it != g[v].end(); ++it) // 遍历v相邻点*it， 
            if (dist[*it] == INT_MAX)            // 如果*it未访问， 
            {
                dist[*it] = dist[v] + 1; prev[*it] = v;    // 调整点*it， 
                que.push(*it);                    // *it入队。 
            }
    }
}

void Print_SP(int v)
{
     if (v != s) Print_SP(prev[v]);
     cout << v << " ";
}

int main()
{
    n = 7;
    g.assign(n, list<int>()); 
    g[0].push_back(1); g[0].push_back(3); 
    g[1].push_back(3); g[1].push_back(4); 
    g[2].push_back(0); g[2].push_back(5); 
    g[3].push_back(2); g[3].push_back(4); g[3].push_back(5); g[3].push_back(6); 
    g[4].push_back(6); 
    g[6].push_back(5);
    
    s = 2;
    USP();
       
    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; 
        }
        
    system("pause");
    return 0;
}

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