图论(三) (一)最短路径算法 2.Dijkstra算法

Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。该算法的时间复杂度是O(N²)，相比于处理无负权的图时，比Bellmad-Ford算法效率更高。

算法描述：

首先引用《算法导论》中的一段比较官方的话，如果可以看懂，那下一部分就可以跳过了：

“Dijkstra算法在运行过程中维持的关键信息是一组结点集合S。从源结点s到该集合中每个结点之间的最短路径已经被找到。算法重复从结点集 V - S 中算则最短路径估计的最小的结点 u ,将 u 加入到集合S，然后对所有从 u 出发的边进行松弛。” 所谓松弛操作，简单的说就是更新两点间的最短距离。

不是很好理解对吧，那么下面的描述是更容易理解的一种描述：

设起始点为s，dis[v]表示s点到v点的最短路径，pre[v]是v的前驱结点，用来输出路径。

1、初始化：dis[v]=∞(v≠s) dis[s]=0,pre[s]=0;

2、for(i=1;i<=n;i++)

(1)在没有被访问过的点中，即上述的V - S集合，找到一个点 u 使得dis[u]是最小的。

(2)标记 u 为已确定的最短路径。

(3)for(每个与 u 相连且没有确定过最短距离的点 v)

if(dis[u]+m[u][v]<dis[v]){

dis[v]=dis[u]+m[u][v];

pre[v]=u;

}

3、结束：结果dis[v]就是s到v的最短距离。

算法理解：

其中自以为有几点理解需要说明：

1、为什么用到中间点？

2、取s到中间点的距离时采用什么策略？

第一个问题，从起点到另一个点的最短路径至少会经历一个中间点，所以我们要求出经过这个中间的到另一个点的路径，就要先求出起点到中间点的最短路径。

第二个问题，其实这里采用的是一中贪心的策略。当然这个策略可以被严格证明是正确的，但是我也一知半解，只知道是可以被证明的，在这里也就不浪费时间了。(详细可以参考《算法导论》)

最后，解释一下为什么有负权边的时候不可以：

连接矩阵如下(图可以自己在旁边画一下)：

1 2 3

1 \ 2 1

2 2 \ -4

3 1 -4 \

那么第一次标记的点就为3并且把dis[3]记为1，但实际上dis[3]应该时-2，因此就会出现错误。

最后附上一段不那么标准的代码：

1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int m[100][100],e,dist[100],n,b[100],pre[100],dist[100];
 4 void dij(int s){
 5      b[s]=1;
 6      int i,j;
 7      for(i=1;i<=n;i++)
 8       dist[i]=m[s][i];
 9      dist[s]=0;
10      pre[s]=0;
11      
12      for(i=1;i<=n;i++){
13       int min=1000000,k=0;
14       for(j=1;j<=n;j++)
15        if(b[j]!=1 && dist[j]<min)
16         {min=dist[j];k=j;}
17        b[k]=1;
18        for(j=1;j<=n;j++)
19         if(min+m[k][j]<dist[j]&&b[j]!=1)
20          {
21           dist[j]=min+m[k][j];
22           pre[j]=i;
23           }                                
24       }
25       for(i=1;i<=n;i++)
26        if(i!=s)
27         printf("%d ",dist[i]);
28      }
29 int main(){
30     int i,j;
31     scanf("%d%d",&n,&e);
32     memset(b,0,sizeof(b));
33     memset(m,10000,sizeof(m));
34     for(i=1;i<=e;i++){
35      int x,y;
36      scanf("%d%d",&x,&y);
37      scanf("%d",&m[x][y]);
38      }
39     int w;
40     scanf("%d",&w);
41     dij(w);
42     system("pause");
43     return 0;
44     }