Dijkstra最短路径
借用HiHo的一个题，来讨论一下单源最短路径问题。
From： HiHoCoder HiHo一下第23周
万圣节的早上，小Hi和小Ho在经历了一个小时的争论后，终于决定了如何度过这样有意义的一天——他们决定去闯鬼屋！
在鬼屋门口排上了若干小时的队伍之后，刚刚进入鬼屋的小Hi和小Ho都颇饥饿，于是他们决定利用进门前领到的地图，找到一条通往终点的最短路径。
鬼屋中一共有N个地点，分别编号为1..N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。那么小Hi和小Ho至少要走多少路程才能够走出鬼屋去吃东西呢？
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为4个整数N、M、S、T，分别表示鬼屋中地点的个数和道路的条数，入口（也是一个地点）的编号，出口（同样也是一个地点）的编号。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^3，M<=10^4, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。
对于100%的数据，满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。
输出
对于每组测试数据，输出一个整数Ans，表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。
样例输入
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1 2 708
2 3 112
3 4 721
4 5 339
5 4 960
1 5 849
2 5 98
1 4 99
2 4 25
2 1 200
3 1 146
3 2 106
1 4 860
4 1 795
5 4 479
5 4 280
3 4 341
1 4 622
4 2 362
2 3 415
4 1 904
2 1 716
2 5 575样例输出
这里先给出AC代码：
1 | #include <fstream> |
讲解Dijkstra算法的文章有很多，算法本身的思想也不难，这里不再多说，主要说明一下关于为何会想到用 “队列” 来加速Dijkstra算法。
请注意上面代码中，findNext 函数中的 返回值 next，以及松弛操作的过程。结合图例说明一下，就很明了了。
原始图状态：
下面规定：在图中，未访问的节点标记为绿色，已访问的节点标记为红色，得到的next节点标记为黄色，经过松弛操作但未访问的节点为青色。源点为 5 号节点。
第一次得到的next：
第一次松弛操作之后：
第二次得到的next：
第二次松弛操作之后：
第三次得到的next：
第三次松弛操作之后：
第四次得到的next：
第四次松弛操作之后：
第五次得到的next：
第五次松弛操作之后：
这样就结束了，得到了源点 5 到途图中所有可达节点的最短路径值。
注意上面步骤的青色节点的变化，优化就是在这个上面做文章了：使用一个队列来维护青色节点，初始状态下，队列只包含起点可达节点，当队列为空的时候，算法结束。
由于next的节点要选取到源点最近的节点，因此应当使用一个优先队列，每次松弛操作之后应当把新增的候选节点加入到该队列中。
下面是AC代码：1
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124#include <fstream>
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)
int N, M, S, T;
vector<vector<int>> graph;
struct Node
{
int index;
int cost;
friend bool operator<(const Node& l, const Node& r);
};
bool operator<(const Node& l, const Node& r)
{
return l.cost > r.cost;
}
int ans = 0;
vector<int> curs;
vector<int> vis;
vector<int> costs;
vector<Node> q;
void solve()
{
while (q.size())
{
make_heap(q.begin(), q.end());
int next = q[0].index;
pop_heap(q.begin(), q.end());
q.pop_back();
for (int i = 1; i <= N; ++i)
{
if (graph[next][i] && 0 == vis[i])
{
int len = costs[next] + graph[next][i];
if (len < costs[i])
{
costs[i] = len;
bool exist = false;
// 修改值
for (auto it = q.begin(); it != q.end(); ++it)
{
if (it->index == i)
{
it->cost = len;
exist = true;
}
}
if (false == exist)
{
Node n;
n.cost = len;
n.index = i;
q.push_back(n);
}
}
}
}
curs.push_back(next);
vis[next] = 1;
}
ans = costs[T];
}
int main(int argc, char** argv)
{
cin >> N >> M >> S >> T;
graph = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
vis = vector<int>(N + 1, 0);
costs = vector<int>(N + 1, INT_MAX);
for (int i = 0; i < M; ++i)
{
int a, b, c;
cin >> a >> b >> c;
if (graph[a][b] == 0)
{
graph[a][b] = c;
graph[b][a] = c;
}
else
{
if (graph[a][b] > c)
{
graph[a][b] = c;
graph[b][a] = c;
}
}
}
curs.push_back(S);
costs[S] = 0;
Node n;
n.cost = 0;
n.index = S;
q.push_back(n);
solve();
cout << ans << endl;
return 0;
}
A*算法
A*算法是一种启发式算法。
在某种程度上，可以将Dijkstra算法视为是一种BFS。BFS的特点就是首先确定搜索边界，并对这个边界上的每一个点进行处理。
如果在处理搜索边界上的点时，能够估计一下它们距离目标结点的开销，并且将其考虑进去，那么就可以提高算法的执行效率。
如果算法使用的启发因子给出的是从任何节点到目标节点的实际开销的下限，那么A*可以保证给出最优解。
最直接的就是计算节点之间的直线距离（笛卡尔坐标系下）。
A*算法的估价函数可以表示为：f’(n) = g’(n) + h’(n)。其中f’(n)是估价函数，g’(n)是起点到终点的最短路径值，h’(n)是节点N到到目标节点的路径的启发值。
以上来源于：Mat Buckland 《游戏人工智编程案例精粹》 以及 王敬东 《游戏地图寻径及地图编辑器的研究》
这里先放上两篇对A*讲解很不错的文章。
两篇文章对A*的工作方式介绍的很清楚，这里就不再多说。只说一下需要注意的一些地方：
- A*所谓的 OPEN（开启） 与 CLOSE（关闭） 表，实际上与前述Dijkstra算法中的红色节点与青色节点一致。
- A*算法的next节点判定实际上是由两个量来决定的：
源点到当前结点的最短路以及当前节点到目标节点的启发值（例如笛卡尔坐标系下的直线距离）。 - 建议先弄清楚Dijkstra算法，然后看第二篇文章，搞清白三个值是怎么起作用的，后面再去看那个英文的专讲。