Posted on 2009-08-28 09:14
reiks 閱讀(280)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;
int n; // n : 頂點個數
vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
int s; // s : 源點(source)
vector<bool> known; // known : 各點是否知道最短路徑
vector<int> dist; // dist : 源點s到各點的最短路徑長
vector<int> prev; // prev : 各點最短路徑的前一頂點
void Dijkstra() // 貪心算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化源點s到自身的路徑長為0。
for (;;)
{
int min = INT_MAX, v = s;
for (int i = 0; i < n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 尋找未知的最短路徑長的頂點v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，將頂點v設為已知，
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > dist[v] + g[v][w])
dist[w] = dist[v] + g[v][w], prev[w] = v; // 調整頂點w的最短路徑長dist和最短路徑的前一頂點 prev。
}
}
void Print_SP(int v)
{
if (v != s) Print_SP(prev[v]);
cout << v << " ";
}
int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = 2; g[0][3] = 1;
g[1][3] = 3; g[1][4] = 10;
g[2][0] = 4; g[2][5] = 5;
g[3][2] = 2; g[3][4] = 2; g[3][5] = 8; g[3][6] = 4;
g[4][6] = 6;
g[6][5] = 1;
s = 0;
Dijkstra();
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;
}
/**//*============優先隊列版================*/
class great
{
public:
bool operator() (pair<int, int>& p1, pair<int, int>& p2) {
return (p1.second > p2.second);
}
};
int G[N][N];
int dijkstra(int src, int dst) {
vector<int> cost(N, INT_MAX);
vector<bool> visited(N, false);
priority_queue< pair<int, int>, vector< pair<int, int> >, great > Q;
cost[src] = 0;
Q.push( make_pair(src, 0) );
while(!Q.empty()) {
pair<int, int> top = Q.top();
Q.pop();
int v = top.first;
if (v == dst) return cost[v];
if (visited[v]) continue;
visited[v] = true;
for(int v2 = 0; v2 < N; v2++) if (G[v][v2] != 0) {
int dist = G[v][v2];
if(cost[v2] > cost[v] + dist) {
cost[v2] = cost[v] + dist;
Q.push( make_pair(v2, cost[v2]) );
}
}
}
return -1;
}