单源最短路——Dijkstara算法

sick

算法基本思想：每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

　　1、将所有的顶点分为两个部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q

　　2、设置源点s到自己的最短路径为0，若存在有源点能够直接到达的顶点i则吧dis设置为e。同时把所有其它不能直接到达的顶点的最短路径设置为∞

　　3、在集合Q的所有顶点中选择一个离源点s最近的顶点u即dis最小，加入到集合P。并考察所有以点u为起点地边，对每条边进行松弛操作。

　　4、重复第三步，直到集合Q为空，算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

1. //dijketra算法
   
2. int main()
   
3. {
   
4.     int e[10][10];
   
5.     int book[10];
   
6.     int dis[10];
   
7.     int i, j, n, m, t1, t2, t3, u, v, min;
   
8.     int inf = 99999999;//用inf存储一个我们认为的正无穷值
   
9. 
   
10.     //读入n和m；n表示定点个数，m表示边的条数
    
11.     scanf("%d%d",&n,&m);
    
12. 
    
13.     //初始化e矩阵
    
14.     for (i = 1; i <= n; i++)
    
15.         for (j = 1; j <= n; j++)
    
16.             if (i == j) e[i][j] = 0;
    
17.             else e[i][j] == inf;
    
18. 
    
19.     // 读入边
    
20.             for (i = 1; i <= m; i++)
    
21.             {
    
22.                 scanf("%d%d%d",&t1,&t2,&t3);
    
23.                 e[t1][t2] = t3;
    
24.             }
    
25.     //初始化dis数组，这里是1号顶点到其余各个顶点的初始路程。
    
26.             for (i = 1; i <= n; i++)
    
27.                 dis[i] = e[1][i];
    
28. 
    
29.     //book数组初始化，book数组用来记录当前点是否被访问，访问1 else0
    
30.             for (i = 1; i <= n; i++)
    
31.                 book[i] = 0;
    
32.             book[1] = 1;//一号顶点标记
    
33. 
    
34.     //核心算法
    
35.             for (i = 1; i <= n - 1; i++)
    
36.             {
    
37.                 //找到离一号顶点最近的顶点
    
38.                 min = inf;//将最小值复制为无穷
    
39.                 for (j = 1; j <= n; j++)
    
40.                 {
    
41.                     //如果当前顶点没有被访问，并且当前dis数组中的值小于最小值
    
42.                     if (book[j] == 0 && dis[j] < min)
    
43.                     {
    
44.                         min = dis[j];//更新最小值
    
45.                         u = j;// 标记当前点
    
46.                     }
    
47.                 }
    
48.                 book[u] = 1;//标记当前点被访问
    
49.                 for (v = 1; v <= n; v++)
    
50.                 {
    
51.                     if (e[u][v] < inf)
    
52.                     {
    
53.                         //遍历u打头的e数组
    
54.                         if (dis[v] > dis[u] + e[u][v])
    
55.                             dis[v] = dis[u] + e[u][v];//获得最短路径
    
56.                     }
    
57.                 }
    
58.             }
    
59.             //输出结果
    
60.             for (i = 1; i <= n; i++)
    
61.             {
    
62.                 printf("%d\t",dis[i]);
    
63.             }
    
64.             getchar(); getchar();
    
65.     return 0;
    
66. }

复制代码