lzm

who dare win.

posts - 14, comments - 29, trackbacks - 0, articles - 0

USP 無權最短路徑算法

Posted on 2009-04-09 10:44 lzmagic 閱讀(2239) 評論(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;

}

只有注冊用戶登錄后才能發表評論。


相關文章: Floyd_Warshall算法 Kruskal算法 Prim算法 Critical Path 關鍵路徑 Bellman_Ford算法 SPFA算法 Dijkstra算法 USP 無權最短路徑算法 Topsort 拓撲排序 (正則表達式)是否匹配(字符串) Quicksort 快速排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

USP 無權最短路徑算法