Dijkstra算法思想

Dijkstra算法思想为：设G=(V,E)是一个带权有向图（无向可以转化为双向有向），把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

 

Dijkstra算法具体步骤　　

（1）初始时，S只包含源点，即S＝{v}，v的距离dist[v]为0。U包含除v外的其他顶点，U中顶点u距离dis[u]为边上的权值（若v与u有边） ）或∞（若u不是v的出边邻接点即没有边<v,u>）。

（2）从U中选取一个距离v(dist[k])最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u∈ U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权(即如果dist[k]+w[k,u]<dist[u]，那么把dist[u]更新成更短的距离dist[k]+w[k,u])。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中(要循环n-1次)

 

Dijkstra算法实现

直接实现

最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为O(n²)

对于空间复杂度：如果只要求出距离，只要n的附加空间保存距离就可以了（距离小于当前距离的是已访问的节点，对于距离相等的情况可以比较编号或是特殊处理一下）。如果要求出路径则需要另外V的空间保存前一个节点，总共需要2n的空间。

/********************************* *   最短路径---Dijkstra算法实现  *   　　　HDU：2544  *   BLOG:www.cnblogs.com/newwy *   AUTHOR:Wang Yong **********************************/  #include 
     
        #define MAX 100  #define INF 1000000000  using namespace std;   int dijkstra (int mat[][MAX],int n, int s,int f)   {       int dis[MAX];       int mark[MAX];//记录被选中的结点        int i,j,k = 0;       for(i = 0 ; i < n ; i++)//初始化所有结点，每个结点都没有被选中            mark[i] = 0;      for(i = 0 ; i < n ; i++)//将每个结点到start结点weight记录为当前distance       {          dis[i] = mat[s][i];          //path[i] = s;      }      mark[s] = 1;//start结点被选中       //path[s] = 0;      dis[s] = 0;//将start结点的的距离设置为0       int min ;//设置最短的距离。       for(i = 1 ; i < n; i++)      {          min = INF;          for(j = 0 ; j < n;j++)          {              if(mark[j] == 0  && dis[j] < min)//未被选中的结点中，距离最短的被选中               {                  min = dis[j] ;                  k = j;              }          }          mark[k] = 1;//标记为被选中           for(j = 0 ; j < n ; j++)          {              if( mark[j] == 0  && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离               {                  dis[j] = dis[k] + mat[k][j];              }          }      }      return dis[f];       }    int mat[MAX][MAX];  int main()  {      int n,m;      while(scanf("%d %d",&n,&m))      {          int a,b,dis;          if(n == 0 || m == 0)              break;          int i,j;          for(i = 0 ; i < n;i++)              for(j = 0 ; j < n; j++)                  mat[i][j] = INF;          for(i = 0 ; i < m ;i++)          {              scanf("%d %d %d",&a,&b,&dis);              --a,--b;              if(dis < mat[a][b] || dis < mat[b][a])              mat[a][b] = mat[b][a] = dis;          }          int ans = dijkstra(mat,n,0,n-1);          printf("%d\n",ans);      }     }
     

二叉堆实现

使用邻接矩阵实现的dijkstra算法的复杂度是O(V²)。使用邻接表的话，更新最短距离只需要访问每条边一次即可，因此这部分的复杂度是O(E).但是每次要枚举所有的顶点来查找下一个使用的顶点，因此最终复杂度还是O(V²)。在|E|比较小时，大部分的时间都花在了查找下一个使用的顶点上，因此需要使用合适的进行优化。

需要优化的是数值的插入(更新)和取出最小值两个操作，因此使用堆就可以了。把每个顶点当前的最短距离用堆来维护，在更新最短距离时，把对应的元素往根的方向移动以满足堆的性质。而每次从堆中取出的最小值就是下一次要用的顶点。这样堆中的元素共有O(V)个，更新和取出的操作有O(E)次，因此整个算法的复杂度是O(ElogV)。 

下面是使用STL的priority_queue实现。在每次更新时往堆里插入当前最短距离和顶点的值对。插入的次数是O(E)次，当取出的最小值不是最短距离的话，就丢弃这个值。这样整个算法也可以在同样的时间内完成。

 

#include 
     
          using namespace std;  /*  * 使用优先队列优化Dijkstra算法  * 复杂度O(ElogE)  * 注意对vector
      
       E[MAXN]进行初始化后加边  */  const int INF=0x3f3f3f3f;  const int MAXN=1000010;  struct qnode  {      int v;      int c;      qnode(int _v=0,int _c=0):v(_v),c(_c){}      bool operator <(const qnode &r)const      {          return c>r.c;      }  };  struct Edge  {      int v,cost;      Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}  };  vector
       
        E[MAXN];  bool vis[MAXN];  int dist[MAXN];  void Dijkstra(int n,int start)//点的编号从1开始  {      memset(vis,false,sizeof(vis));      for(int i=1;i<=n;i++)dist[i]=INF;      priority_queue
        
         que;      while(!que.empty())que.pop();      dist[start]=0;      que.push(qnode(start,0));      qnode tmp;      while(!que.empty())      {          tmp=que.top();          que.pop();          int u=tmp.v;          if(vis[u])continue;          vis[u]=true;          for(int i=0;i
         
          dist[u]+cost)              {                  dist[v]=dist[u]+cost;                  que.push(qnode(v,dist[v]));              }          }      }  }  void addedge(int u,int v,int w)  {      E[u].push_back(Edge(v,w));  }  int main()  {      int n,m;      int T;      scanf("%d",&T);      while(T--)      {          scanf("%d%d",&n,&m);          for(int i=1;i<=n;i++)E[i].clear();          for(int i=0;i