最短路径计算分静态最短路计算和动态最短路计算。
静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*（A Star）算法。 动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。如在游戏中敌人或障碍物不断移动的情况下。典型的有D*算法
Dijkstra算法
Dijkstra算法求最短路径：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
4
5Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。
6
7大概过程：
8创建两个表，OPEN, CLOSE。
9OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
101． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
112． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
123． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
134． 重复2，3，步。直到OPEN表为空，或找到目标点。
14
15
这是在drew 程序中4000个节点的随机路网上Dijkstra算法搜索最短路的演示，黑色圆圈表示经过遍历计算过的点由图中可以看到Dijkstra算法从起始点开始向周围层层计算扩展，在计算大量节点后，到达目标点。所以速度慢效率低。
提高Dijkstra搜索速度的方法很多，据Drew所知，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。
- 基本思想
引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
- 操作步骤
(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4) 重复步骤(2)和(3)，直到遍历完所有顶点。
单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
2测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大
31000000 1000000 10 100000 30 100
41000000 5 1000000 1000000 1000000
51000000 1000000 50 1000000 1000000
61000000 1000000 1000000 1000000 10
71000000 1000000 20 1000000 60
81000000 1000000 1000000 1000000 1000000
9结果：
10D[0] D[1] D[2] D[3] D[4] D[5]
11 1000000 10 50 30 60
12*/
13#include <stdio.h>
14#define MAX 1000000
15
16int arcs[10][10];//邻接矩阵
17int D[10];//保存最短路径长度
18int p[10][10];//路径
19int final[10];//若final[i] = 1则说明 顶点vi已在集合S中
20int n = 0;//顶点个数
21int v0 = 0;//源点
22int v,w;
23void ShortestPath_DIJ()
24{
25 for (v = 0; v < n; v++) //循环 初始化
26 {
27 final[v] = 0; D[v] = arcs[v0][v];
28 for (w = 0; w < n; w++) p[v][w] = 0;//设空路径
29 if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;}
30 }
31 D[v0] = 0; final[v0]=1; //初始化 v0顶点属于集合S
32 //开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中
33 for (int i = 1; i < n; i++)
34 {
35 int min = MAX;
36 for (w = 0; w < n; w++)
37 {
38 //我认为的核心过程--选点
39 if (!final[w]) //如果w顶点在V-S中
40 {
41 //这个过程最终选出的点 应该是选出当前V-S中与S有关联边
42 //且权值最小的顶点 书上描述为 当前离V0最近的点
43 if (D[w] < min) {v = w; min = D[w];}
44 }
45 }
46 final[v] = 1; //选出该点后加入到合集S中
47 for (w = 0; w < n; w++)//更新当前最短路径和距离
48 {
49 /*在此循环中 v为当前刚选入集合S中的点
50 则以点V为中间点 考察 d0v+dvw 是否小于 D[w] 如果小于 则更新
51 比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
52 */
53 if (!final[w] && (min+arcs[v][w]<D[w]))
54 {
55 D[w] = min + arcs[v][w];
56 // p[w] = p[v];
57 p[w][w] = 1; //p[w] = p[v] + [w]
58 }
59 }
60 }
61}
62
63
64int main()
65{
66 freopen("./Dijkstra.txt", "r", stdin);
67 scanf("%d", &n);
68 for (int i = 0; i < n; i++)
69 {
70 for (int j = 0; j < n; j++)
71 {
72 scanf("%d", &arcs[i][j]);
73 }
74 }
75 ShortestPath_DIJ();
76 for (int i = 0; i < n; i++) printf("D[%d] = %d\n",i,D[i]);
77 return 0;
78}
79
80
2
3
4
5
6
7
8
21000000 5 1000000 1000000 1000000
31000000 1000000 50 1000000 1000000
41000000 1000000 1000000 1000000 10
51000000 1000000 20 1000000 60
61000000 1000000 1000000 1000000 1000000
7
8
A*(A Star）算法：启发式（heuristic）算法
A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，即起始节点到当前节点的实际代价.
h(n)是从n到目标节点最佳路径的估计代价。即当前节点到目标节点的估计代价.
例如：当h(n) = 0, g(n) = d, 则f(n) = g(n)就变为了宽度优先搜索，也就是如果不需要启发，那就是宽度优先搜索的算法了。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
- 估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
- 如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
- 估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)(dx-nx)+(dy-ny)(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2{
3从OPEN表中取估价值f最小的节点n;
4if(n节点==目标节点) break;
5else
6{
7if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
8if( X的估价值小于OPEN表的估价值 )
9 更新OPEN表中的估价值; //取最小路径的估价值
10
11if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
12if( X的估价值小于CLOSE表的估价值 )
13 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
14
15if(X not in both)
16求X的估价值;
17 并将X插入OPEN表中; //还没有排序
18}
19
20将n节点插入CLOSE表中;
21按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
22}
23
24
上图是和上面Dijkstra算法使用同一个路网，相同的起点终点，用A*算法的情况，计算的点数从起始点逐渐向目标点方向扩展，计算的节点数量明显比Dijkstra少得多，效率很高，且能得到最优解。
A算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A算法中估价值为0的情况。
Floyd（弗洛伊德）算法( from JarryWell)
Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。两次遍历，时间复杂度较高。
算法思想
从任意节点i到任意节点j的最短路径不外乎2种可能：1)直接从节点i到节点j，2)从节点i经过若干个节点k到节点j。所以，我们假设arcs(i,j)为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立，如果成立，证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短，我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j)，这样一来，当我们遍历完所有节点k，arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。（由于动态规划算法在执行过程中，需要保存大量的临时状态（即小问题的解），因此它天生适用于用矩阵来作为其数据结构，因此在本算法中，我们将不使用Guava-Graph结构，而采用邻接矩阵来作为本例的数据结构）
2
3
4
5
6
7
8
9
10
11
12
2 for (int i = 1; i <= vexCount; i++) {
3 for (int j = 1; j < vexCount; j++) {
4 if (arcs[i][k] + arcs[k][j] < arcs[i][j]) {
5 arcs[i][j] = arcs[i][k] + arcs[k][j];
6 path[i][j] = path[i][k]; //这里保存当前是中转的是哪个节点的信息
7 }
8 }
9 }
10}
11
12
几个常用最短路径算法的比较
