改进迪杰斯特拉算法（dijkstra）：输出所有最短路径

对于权值非负的图求解单源最短路径，第一想法是使用dijkstra算法。最短路径问题是满足最优子结构的：父问题一定会使用子问题的最优解。问题在于子问题的计算次序。dijkstra算法思想建立在我们为无负权图定义的子问题计算顺序基础上：即离源点最近点不会变成其他问题的子问题，其他问题只能成为他的子问题。

​本次实验在实现dijkstra算法的基础上：

• 构建基于邻接表的图类：Graph.class，便于以后实验复用。
• 此外加入了优先队列进行优化
• 不仅实现对最优解（最短路径）的记录而且对所有的最优解（所有的最短路径）进行输出。

本次实现额外实现部分：

• 实现基于邻接表的Graph数据结构
• 堆优化：将时间复杂度优化到$nlg(n)$
• 输出【所有的最短路径】：需要花费额外的时间复杂度（一般的dijkstra不需要输出所有的最短路径，只需要输出一条，本实验输出了所有的最短路径）

程序如下：

//
// Created by BlancheSun on 2022/4/10.
//

#include
#include
#include 
#include 

using namespace std;

class ArcNode{
public:
    int adjvec;
    double weight;
    ArcNode(int adjvec, double weight) : adjvec(adjvec), weight(weight){};
    ArcNode() {};
    friend bool operator<(const ArcNode& arc1, const ArcNode& arc2) {
        return arc1.weight > arc2.weight;
    }
};

class Graph{
private:
    int vexnum; // 顶点数
    int arcnum; // 边数
    vector<vector<ArcNode>> arcList;   // 矩阵存储结点之间的连接关系
public:
    Graph(int vexnum, int arcnum);
    Graph();
    void add_edge(int start, int end, double weight);
    void dijkstra(int source, int target);
    void recordShortestPath(vector<vector<int>>& pre, int target, vector<vector<int>>& path, vector<int> temp_path);
    void printAllPath(vector<vector<int>>& path, vector<double>& dis, int source, int target);
};

void Graph::add_edge(int start, int end, double weight){
    arcList[start].push_back(ArcNode(end, weight));
    arcList[end].push_back(ArcNode(start, weight));
}

void Graph::dijkstra(int source, int target) {
    // 初始化操作
    int n = this->vexnum;
    int inf = 99999.0;
    vector<double> dis(n, inf);
    dis[source] = 0;
    vector<vector<int>> pre(n,vector<int>(0));
    priority_queue<ArcNode> nodeQueue;
    nodeQueue.push(ArcNode(source, 0));

    // 队列非空时进行检索
    while(!nodeQueue.empty()) {
        int node = nodeQueue.top().adjvec;  // 获得目前队列中距离源点最近的结点
        double weight = nodeQueue.top().weight;  // 或者写成 weight = nodeQueue.top().weight
        nodeQueue.pop();    // 取出队列中的元素

        if(node == 3||node == 5) {
            int m = 1;
        }
        // 从该结点出发，更新该结点能直接相连的结点
        for(int i = 0; i < arcList[node].size(); i++) {
            int v = arcList[node][i].adjvec;
            if (weight + arcList[node][i].weight < dis[v]) {    // 越界了！
                dis[v] = weight + arcList[node][i].weight;
                pre[v] = {node};                          // 记录上一步的结点
                nodeQueue.push(ArcNode(v, dis[v]));
            }else if(weight + arcList[node][i].weight == dis[v]) {
                pre[v].push_back(node);
            }
        }
    }
    vector<vector<int>> path;    // 初始大小的为0,
    vector<int> temp_path;
    recordShortestPath(pre, target, path, temp_path);   // 运行后path_index数值即为路径条数，不用加一，程序中已经加一
    printAllPath(path, dis, source, target);

}

Graph::Graph(int vexnum, int arcnum) : vexnum(vexnum), arcnum(arcnum) {
    // 做容量的初始化
    vector<vector<ArcNode>> V(vexnum, vector<ArcNode>());
    this->arcList = V;
}

Graph::Graph() {}

/** 第k条路径的记录 **/
void Graph::recordShortestPath(vector<vector<int>> &pre, int target, vector<vector<int>>& path, vector<int> temp_path) {
    vector<int> now_pre = pre[target];  // 获得当前节点的前驱结点集合
    temp_path.push_back(target);
    if(now_pre.empty()) {   // 没有前驱结点
        path.push_back(temp_path);
        return;
    }
    // 不为空，那么深搜前驱结点，得到路径
    for(int i = 0; i < now_pre.size(); i++) {
        int target2 = now_pre[i];   // 集合中的一个点
        recordShortestPath(pre, target2, path, temp_path);
    }
}

/** 打印所有的路径 **/
void Graph::printAllPath(vector<vector<int>> &path, vector<double>& dis, int source, int target) {
    cout << "The shortest path(es) from node " << source << " to node " << target << " are/is as follows: " << endl;
    int k = path.size();    // 路径的条数
    for(int i = 0; i<k; i++) {
        cout << "Path" << i << ": " ;
        for(int j = path[i].size()-1; j > 0 ; j--) {
            cout << path[i][j] << " -> ";
        }
        cout << path[i][0] << endl;
    }
    cout << "The length of path(es) is " << dis[target] <<endl;
}

int main() {
	// 多条最短路径的测试
    Graph graph = Graph(9, 14); // 9个顶点，14条边

    // 边的添加
    graph.add_edge(0,1,1);
    graph.add_edge(0,7,8);
    graph.add_edge(1,2,8);
    graph.add_edge(1,7,11);
    graph.add_edge(2,3,3);
    graph.add_edge(2,5,4);
    graph.add_edge(2,8,2);
    graph.add_edge(3,4,9);
    graph.add_edge(3,5,1);
    graph.add_edge(4,5,10);
    graph.add_edge(5,6,2);
    graph.add_edge(6,7,1);
    graph.add_edge(6,8,6);
    graph.add_edge(7,8,7);

    int source = 0, target = 4;
    graph.dijkstra(source, target);
    
//    Graph graph = Graph(16, 30); // 16个顶点，30条边
//
//    // 边的添加
//    graph.add_edge(0,2,3);
//    graph.add_edge(1,3,1);
//    graph.add_edge(1,4,3);
//    graph.add_edge(1,5,6);
//    graph.add_edge(2,4,8);
//    graph.add_edge(2,5,7);
//    graph.add_edge(2,6,6);
//    graph.add_edge(3,7,6);
//    graph.add_edge(3,8,8);
//    graph.add_edge(4,7,3);
//    graph.add_edge(4,8,5);
//    graph.add_edge(5,8,3);
//    graph.add_edge(5,9,3);
//    graph.add_edge(6,8,8);
//    graph.add_edge(6,9,4);
//    graph.add_edge(7,10,2);
//    graph.add_edge(7,11,2);
//    graph.add_edge(8,11,1);
//    graph.add_edge(8,12,2);
//    graph.add_edge(9,11,3);
//    graph.add_edge(9,12,3);
//    graph.add_edge(10,13,3);
//    graph.add_edge(10,14,5);
//    graph.add_edge(11,13,5);
//    graph.add_edge(11,14,2);
//    graph.add_edge(12,13,6);
//    graph.add_edge(12,14,6);
//    graph.add_edge(13,15,4);
//    graph.add_edge(14,15,3);
//
//
//    // 求解最短路径
//    int source = 0, target = 15;
//    graph.dijkstra(source, target);

    return 0;
}
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

以下图为例进行执行

结果如下：可见所有的最短路径都被输出

1. 基于邻接表的Graph

​ 基础的邻接矩阵也能作为dijkstra算法的数据结构，但是对于稀疏图或者结点很多的情况下输入数据较为复杂且容易超出内存。本次实验使用邻接表实现图的数据结构，主要设置如下：

• ArcNode.class：邻接表的表结点。含有表结点的终点编号adjvec和边权重weight两个属性。

• vector> ArcList：

  • ArcList[i]表示结点i为起点的所有表结点的集合

• Graph.class：

  含有三个属性：

  • vexnum：结点数
  • arcnum：边数
  • vector> ArcList：邻接表

  含有四个方法：

  • add_edge(int start, int end)：向邻接表中增加表结点

  • dijkstra(int source, int target)：计算最短路径和所有结点的前驱结点集合，以求得所有最短路径

  • recordShortestPath(vector> &pre, vector>& path：根据dijksra中的前驱结点集合pre，进行深度优先搜索，得到所有的最短路径，存入path数组中。

  • printAllPath(vector> &path)：打印所有的最短路径

2 基本算法思路说明与堆优化

（1）基本思路

dikstra算法的核心过程很简单，主要特点是使用广度优先搜索。算法主要过程如下：

• 初始化：
  • 集合初始化：设置已松弛集合$T=\varnothing$，和未松弛集合 U = { s 0 , s 1 . . . , s n } U = \{s_0,s_1...,s_n\} U={s0​,s1​...,sn​}全部n个结点。
  • 距离数组初始化：设置有大小为结点个数n的距离数组$vector<int>dis(n,+\infty )$，另外将$dis[s_0]$初始化为0。
• 循环n轮：每次扩展扩展使用不在集合$T$中（在集合$U$中），且距离源点$s_0$最近的结点$s_k$对所有与$s_k$直接相联的结点$s_j$进行松弛，第一轮时即使用$s_0$进行松弛。松弛条件为：

{ v i s i t e d [ s j ] = = f a l s e : s j 为被用来松弛过 d i s [ s k ] + w e i g h t ( s k , s j ) < d i s [ s j ]

{visited[sj​]==false:sj​为被用来松弛过dis[sk​]+weight(sk​,sj​)<dis[sj​]​

​ 满足条件即更新$dis[s_j]=dis[s_k]+weight(s_k,s_j)$。更新完后将$s_k$加入集合T，从U中移出$s_k$。

​ 从动态规划的角度看，上式也可以理解成动态规划的递推式。

• 循环结束：每个结点都被加入$T$，此时的$dis[n]$即为最短距离。

（2）堆优化

在（1）的步骤二循环n轮中，每次循环需要寻找距离源点$s_0$最近的结点。若是采取循环扫描一遍的过程，那么dijkstra算法的时间复杂度将会为$O(n^2)$，仔细分析，该过程寻找最近距离的过程有下面的特点：

• 集合大小是动态变化的结点
• 每次从集合中寻找的距离最小的元素，不需要所有的元素有序

符合这样的特点我们可以用堆进行优化。即：

• ① 将遍历$dis[s_k]$寻找最小值的过程使用一个优先队列$nodeQueue$的top()和pop()操作代替。同时$visted$数组变得不再需要，因为该结点被$pop()$，下轮更新队列中将不会存在该结点。
• ② 每次对松弛对$dis[v]$进行操作时，同时需要向优先队列中减小该结点的$weight$。

3 实现多条最短路径记录

3.5.3.1 路径的记录

如果只需要记录一条最短路径，那么我们在进行松弛操作后用一个数组$pre[n]$记住用于松弛该结点的$s_k$即可。即：
$$pre[s_j]=s_k$$
我们这里实现了多条最短路径的输出，一维数组不再能满足我们的要求，我们需要一个二维数组$pre[n][m]$记录所有的前驱结点。对于一个结点编号为$i$的结点，其所有的前驱为$pre[i]$集合中的所有元素。当然，如果最短路径只有一条，那么$pre[i]$中只有一个元素。

另外，需要存储多条最短路径后，在松弛时进行的操作和只输出一条路径时不相同：

• 若$dis[s_k]+weight(s_k,s_j)<dis[s_j]$：

  直接将$pre[s_j]$置为$s_k$的编号，然后将队列中修改$s_j$的权重为$dis[s_k]+weight(s_k,s_j)$，更新$dis[s_j]=dis[s_k]+weight(s_k,s_j)$

• 若$dis[s_k]+weight(s_k,s_j)==dis[s_j]$

  向$pre[s_j]$中增加$s_k$的编号

3.1 路径的输出

按照上述的方式进行记录后，我们最终得到的$pre$数组，为了便于说明，我们给出下面的一个例子：

图18：pre数组举例

以图中的结点4为例，我们给出他的$pre$数组树：

图19：pre数组树

根据这棵$pre$数组树，我们能够通过深度优先遍历的方式得到从结点4开始到源点0的所有的最短路径。在深搜过程中我们每得到一条路径就应该将他存在一个二维的$path$数组，每一维存储一条路径。在得到所有最短路径后，遍历$path$数组的每个元素，每一个元素即是一条路径的路径数组，逐条打印出路径结果即可。