Chinaunix首页 | 论坛 | 博客
  • 博客访问: 112579
  • 博文数量: 61
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 261
  • 用 户 组: 普通用户
  • 注册时间: 2014-07-08 11:29
文章分类

全部博文(61)

文章存档

2016年(9)

2015年(36)

2014年(16)

我的朋友

分类: C/C++

2015-06-23 18:14:30

    Dijkstra算法是求单源最短路径好方法,但是只能处理没有负边的图的问题,有一条边为负的就会导致最终的结果不正确
   时间复杂度可以达到O(|E|log|v|), 所以一般求单源最短路径问题都可以用这个算法
   伪代码:
   priority_queue que;
   que.push(startV);
   while que is not empty
        V a = que.top();
          que.pop();
        for all V connect with a:
            if d(v) > d(a) + length_a_to_v;
               d(v) = d(a) + length_a_to_v;
               que.push(v);

    直接上代码:
    

点击(此处)折叠或打开

  1. #include <functional>
  2. #include <queue>
  3. using namespace std;
  4. #define MAXV 4
  5. #define INF 100000
  6. int d[4] = { 0 };
  7. int edge[4][4] = { 0 };
  8. void init()
  9. {
  10.     for (int i = 0; i < MAXV; i++)
  11.         for (int j = 0; j < MAXV; j++)
  12.             edge[i][j] = INF;
  13.     edge[0][0] = 0;
  14.     edge[0][1] = 6;
  15.     edge[0][2] = 1;
  16.     edge[1][3] = 2;
  17.     edge[2][3] = 8;
  18.     edge[3][0] = 3;
  19. }

  20. typedef pair<int, int> p;



  21. void dijsktra(p s)
  22. {
  23.     priority_queue<p, vector<p>, greater<p>> que;
  24.     que.push(s);
  25.     while (!que.empty())
  26.     {
  27.         p tmp = que.top();
  28.         que.pop();
  29.         for (int i = 0; i < MAXV; i++)
  30.         {
  31.             if (tmp.first != i)
  32.             {
  33.                 if (edge[tmp.first][i] != INF && (d[i] > d[tmp.first] + edge[tmp.first][i]))
  34.                 {
  35.                     d[i] = d[tmp.first] + edge[tmp.first][i];
  36.                     p newP;
  37.                     newP.first = i;
  38.                     newP.second = d[i];
  39.                     que.push(newP);
  40.                 }
  41.             }
  42.         }
  43.         
  44.     }
  45.     for (int i = 0; i < MAXV; i++)
  46.     {
  47.         printf("%d",d[i]);
  48.     }

  49. }

  50. int _tmain(int argc, _TCHAR* argv[])
  51. {
  52.     fill(d, d + 4, INF);
  53.     
  54.     init();
  55.     d[0] = 0;
  56.     p s;
  57.     s.first = 0;
  58.     s.second = d[0];
  59.     dijsktra(s);
  60.     
  61.     return 0;
  62. }



     
阅读(354) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~