算法分析与设计：实验4实验报告

前三次实验的链接是：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 等）。

三、实验内容及要求

• 描述并实现单源最短路径算法，显示在下图上的运算结果
  
• 描述并实现全点对最短路径算法，显示在下图上的运算结果
  

四、思考题

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

实验分析

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

单源最短路算法

主要有 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 算法的核心思想就是上面说到的动态规划。

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

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

思考题

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

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 这种必须要使用矩阵存边的算法的时候，使用链式前向星存图是最优解。

后记

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