抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

ひと結び、人を結んで

前三次实验的链接是:https://shiraha.cn/2020/class-algorithm-experiment-report-1-3/

这次实验的代码也在:https://dev.azure.com/Pure-Asahi/2020_Spring_In_Class_Job

实验四:最短路算法

实验要求如下:

#####
实验四:单源最短路径和全点对最短路径算法

一、实验目的 掌握复杂数据结构的存储和操作方法,实现图的搜索。

二、实验条件 计算机及程序语言开发平台(如 C、C++、Java、Matlab 等)。

三、实验内容及要求

  • 描述并实现单源最短路径算法,显示在下图上的运算结果 0ILCRWV_JPT9YMQ9AY~O5L.png
  • 描述并实现全点对最短路径算法,显示在下图上的运算结果 8_BFK_UFOO~RD6_KVH_XGB5.png

四、思考题 - 全点对最短路径算法动态规划算法范式 - 图的存储方式和运算效率之间的关系

实验分析

下面分析两个任务可以采用的算法。

单源最短路算法

主要有 Bellman-Ford 算法、DAG 算法、Dijkstra算法。

Bellman-Ford 算法的主要思想即是对所有的边进行 V-1 次的遍历,每次对 每一条边执行一次缩短操作,缩短操作的核心就是判断 d[v] > d[u] + w(u, v),如果是的话则更新 d[v],否则不变。算法结 束后还需要进行回路检测,如果存在负回路则返回 false,否则返回真,该算法较为简单,运行开销函数是 O(VE)。基于这个算法还有中国教授进行队列优化的SPFA算法,在一般情况下效率高于 Bellman-Ford 算法,但是最坏不会差于 Bellman-Ford 算法。

DAG 算法是针对图为有向无环图的特殊情况,显然它要求没有回路。这个算法首先需要对图进行拓扑排序,完成后再进行初始化,再根据拓扑排序的顶点顺序对邻接边进行 缩短操作,缩短操作同方法一。如果排序过程中出现不需要的边,只要更新父节点即可。运行时间开销是 O(V+E),但是该算法限制较大,只能在图又这种特殊性质的情况下才可以使用。但是也可以使用 Tarjan 缩点,对于每个SCC内部再求最短路之后再使用这个算法,这样的话效率就不能保证了。

Dijkstra 算法要求不存在负权值的边,首先把所有节点压入队列 Q 中,然后每次让节点权值最小的节点出队,然后对其临接节点执行缩短操作,Q 为空时即结束。时间复杂度是 O(V*lgV+E)。实际实现的时候,可以使用堆进行贪心优化,使得实现的算法速度更快。

全点对最短路径算法

可以进行n次单源最短路径算法,也可以进行动态规划。

进行n次单源最短路径算法并不经济。单源最短路算法的复杂度大多和 E 相关,但是 E 的上限可以是 V²。当待解决问题的图是一个稠密图的时候,n次单源最短路径算法将会退化到 O(V³·logV) 甚至是 O(V⁴),这是非常不好的。

动态规划法对于稠密图而言是很好的,唯一的缺点是会占用一定的空间:通过建立一个V*V的数组进行递推得到答案。这样做的正确性在于:最短路径的部分路径必然是最短的。因此,通过多个最短部分路径就可以找到全路径的最小值,每一个找到的部分最短路径也是它端点的最短值,没有进行重复的查找,时间复杂度是 O(V³)。经典的实现就是 Floyd 算法,它就是 O(V³) 的。

算法实现

首先,我们将图的边描述出来;点的编号从 1 开始,{u, v, w} 代表从 u 出发到达 v 的边,边权是 w。

单源最短路径的图可以这样描述:

1
2
3
4
5
6
7
8
9
10
1 2 6  
1 4 7
2 3 5
2 5 -4
2 4 8
3 2 -2
4 3 -3
4 5 9
5 1 2
5 3 7

起点是点 1.

全点对最短路径的图可以这样描述:

1
2
3
4
5
6
7
8
9
1 2 3
1 3 8
1 5 -4
2 4 1
2 5 7
3 2 4
4 1 2
4 3 -5
5 4 6

上述数据将作为算法实现的输入。

对于单源最短路问题,因为题目所给的图包含负边权,所以不能够使用堆优化的Dijkstra算法,因此实现为使用了队列优化的SPFA算法。因为图并不算是稠密图,使用链式前向星存储图。使用memset可以设置的可加和的最大值0x3f3f3f3f3f3f3f3f作为INF值。

这里是链式前向星的简单实现,由于C++特性避免动态分配内存,限制了最大顶点数为100:

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
struct edge {
int u, v, w;
int next;
edge() = default;
edge(int u, int v, int w, int next)
:u(u), v(v), w(w), next(next) {}
};

const int N = 100;

struct fws {
int head[N + 1]{};
int tot{};
edge ee[(N + 1) * (N + 1) * 2]{};

fws() {
memset(head, -1, sizeof head);
tot = 0;
}

void addEdge(int u, int v, int w) {
ee[tot] = edge(u, v, w, head[u]);
head[u] = tot ++;
}

edge &getEdge(int index) {
return ee[index];
}
};

然后就是最短路的核心算法SPFA的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
long long *spfa(fws &graph, int start, int n) {
if (start < 0 || start > n) return nullptr;
auto *ans = new long long[n + 1];
std::queue<int> heap;
bool visit[N + 1] { 0 };
memset(ans, 0x3f, sizeof(long long) * (n + 1));
heap.push(start);
visit[start] = true;
ans[start] = 0;
while (!heap.empty()) {
auto now = heap.front();
heap.pop();
visit[now] = false;
for (auto ii = graph.head[now]; ~ii; ii = graph.getEdge(ii).next)
if (ans[now] + graph.getEdge(ii).w < ans[graph.getEdge(ii).v]) {
ans[graph.getEdge(ii).v] = ans[now] + graph.getEdge(ii).w;
if (!visit[graph.getEdge(ii).v]) {
heap.push(graph.getEdge(ii).v);
visit[graph.getEdge(ii).v] = true;
}
}
}
return ans;
}

每次搜索到邻接的边的时候,就观察它是否能缩短到达新边终点的距离;如果可以,那就对这个节点进行进一步松弛,将它加入队列;执行结果可以看后面。

对于全点对最短路问题,可以使用矩阵记录每两个顶点之间的最短路径,并且使用 Floyd 算法完成最短路径的计算。下面是核心的 Floyd 算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long **floyd(long long **graph, int n) {
auto a = new long long*[n + 1];
for (int i = 1; i <= n; ++ i) {
a[i] = new long long[n + 1];
memset(a[i], 0x3f, sizeof(long long) * (n + 1));
}
for (int k = 1; k <= n; ++ k)
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
a[i][j] = std::min(
std::min(a[i][j], a[i][k] + a[k][j]),
std::min(graph[i][j], graph[i][k] + graph[k][j])
);
return a;
}

Floyd 算法的核心思想就是上面说到的动态规划。

上述的两个算法输入样例后的输出如下:

KNJaS4KXVZTGXQU6R2IY_W.png

显然,这些答案是正确的。

思考题

全点对最短路径算法动态规划算法范式

Step1:描述最优解的结构特征:最短路径的部分路径必然是最短的

Step2:定义最优解决方案的递归形式 \[ \begin{cases} m = 0: l_{i,j}^{(0)} = \begin{cases} 0 ,& i = j \\ ∞ ,& i \ne j \end{cases} \\ m \ge 1: l_{i,j}^{(m)} = min_{1\le k\le n} \ l_{i,k}^{(m-1)}+w_{k,j} \end{cases} \] Step3:以自底向上的方式计算优解决方案的值:从最多只有 0 条边开始,一直计算到最多有 V-1 条边结束

Step4:从计算信息构造出优解决方案 由于不必计算所有 L(m),而且如果没有负回路,可以得到: L(m) = L(n - 1) 对所有 m >= n – 1 成立,所以我们可以通过下式计算: \[ L^{(2n)} = W^{2n} = W^n \cdot W^n \]

图的存储方式和运算效率之间的关系

选择合适的数据结构,当然可以提高运算的效率;比如若采用矩阵的方式存储边集,如果在边不密集的情况下,那么有很多的空间将被浪费;除此之外,当遍历矩阵时,会有很多的无效遍历;所以对于稀疏图而言,链式前向星将是一种更加有效的方法:既不会很浪费空间(甚至在很多情况下比邻接矩阵还要节约空间),也可以很快的遍历;对于存在双向边的图而言,使用链式前向星还可以方便的通过^1找到边的反向边,还可以直接顺序遍历所有的边,从而为很多算法做好了基础。

在绝大多数的情况下,如果不是图比较稠密或者使用 Floyd 这种必须要使用矩阵存边的算法的时候,使用链式前向星存图是最优解。

后记

最后一次的算法比较板子,没什么代码量。最短路是很基础的算法了,但是很多思想都可以在其他的地方使用。即使是最短路算法的题目,也可以出的非常花哨。

评论