Reiks的技术博客

C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

日历

<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

搜索

  •  

最新评论

Dijkstra

Posted on 2009-08-28 09:14 reiks 阅读(256) 评论(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<intint>& p1, pair<intint>& 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<intint>, vector< pair<intint> >, great > Q;

        cost[src] 
= 0;
        Q.push( make_pair(src, 
0) );

        
while(!Q.empty()) {
                pair
<intint> 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;
}


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