1.问题分析
给定有向带权图G = (V, E),其中每条边的权是非负实数。此外，给定V中的一个顶点u,称为源点。现在要计算从源到所有其它各顶点的最短路径，这里的路径指的是路径上各边的权值之和。
求单源最短路径的算法是Dijkstra，荷兰人，计算机科学家，在1972年获得图灵奖。
2.算法设计
Dijkstra是解决单源最短路径的贪心算法。算法的基本思想首先假定源点为u，顶点集合V被划分为两部分：集合S和集合V-S。初始时S中仅含有源点u，源点u到集合V-S中包含的顶点的最短路径待定。我们把从源点出发只经过S中的点到达V-S中的点的路径称为特殊路径，并用数组dist[]记录当前源点到每个点所对应的特殊路径的长度。
Diskstra算法采用的贪心策略是选择特殊路径长度最短的路径，将其连接的V-S中的顶点加入到集合S中，同时更新数组dist[]。一旦S中包含了所欲顶点，dist[]就是从源点到其它顶点之间的最短路径长度。
算法需要维护的数据结构有三个( 理解数据结构的意义是重点！)：
邻接矩阵graph[][]：用来保存相邻顶点边上的权值,如果两个顶点之间没有边相连，则它们之间的权值为无穷大；
最短距离数组dist[i]：用来记录点i的最短路径长度；
前驱数组pre[i]：用来记录最短路径上顶点i的前驱；
选中顶点数组isIn[i]：bool类型，用来表示顶点i当前是否被选中。
算法执行流程
初始化。令集合S = {u}，初始化graph[][]，对于集合V-S中的所有顶点i,初始化dist[i] = map[u][i], 如果源点到顶点i之间有边相连，初始化pre[i] = u，否则pre[i] = -1。同时令isIn[u] = true,表示选中，其它顶点都设为false；(1)
找最小。在集合V-S中找出离源点最近的，就是在dist[]中找到值最小的顶点m，但前提是isIn[m]=false；(2)
将选中的顶点j加入到集合S中，同时更新V-S，这一步操作实际就是令isIn[m] = true；(3)
更新路径。选中顶点j后，需要判断和j相连的其它顶点k通过走顶点j是否可以缩短到源点到距离，即是否有“捷径”可走。如果dist[k] > dist[m] + graphm,说明有“捷径”可走，则更新dist[k] = dist[m] + graphm,同时更新顶点k的前驱，零pre[k] = m；(4)
判断S-V集合中是否为空，如果为空，算法结束，否则转到流程(3)继续选择；(5)
由此，可求得从源点u到图G的其余各个顶点的最短路径及长度，并且可以通过数组pre[]回溯找到最短路径上依次经过的顶点。
算法图解
(1) 原始数据结构
(2) 初始化最短距离数组dist[][]和前驱数组pre[]
(3) 找dist[]值最小的顶点并加入集合S
(4) 更新路径
(5) 继续找dist[]值最小的顶点并加入集合S
(6) 更新路径
(7) 继续找dist[]值最小的顶点并加入集合S
(8) 更新路径(此次没有数据需要更新！)
(9) 继续找dist[]值最小的顶点并加入集合S
(10) V-S={}为空，算法结束。
由此，可求得从源点u到图中其它各个顶点的最短路径，并且可以通过前驱数组pre[]逆向找到路径上经过的节点。例如，p[5] = 3,通过图10的前驱数组可得到源点1到5的最短路径为1->2->3->5。
3.代码片段详解
(会意即可，相关的数据结构在后面代码中会详细展示!)
初始化最短距离数组dist[][]和前驱数组pre[]
flag[u] = true;
dist[u] = 0;
for (int i = 1; i <= n; i++) {
dist[i] = graph[u][i];
isIn[i] = false;
if (dist[i] == INF)
pre[i] = -1;
else
pre[i] = u;
}
找dist[]值最小的顶点并加入集合S
int tmp = INF, m = u; // m为{V-S}中要找的距离源点u最近的顶点
for (int i = 1; i <= n; i++) {
if (!isIn[i] && dist[i] < tmp) {
m = i;
tmp = dist[i];
}
}
// 如果找不到j(flag[]全为true,顶点已经全部找完),结束
if (m == u) return;
// 如果找到，将t加入集合S
isIn[m] = true;
更新路径
// 更新路径(m为当前选择的离源点u最近的顶点)
for (int i = 1; i <= n; i++) {
// !isIn[i] = false表示顶点i在集合V-S中
// graph[m][i] 表示顶点i顶点m邻接(即m->i有边存在)
if (!isIn[i] && graph[j][i] < INF) {
// 经过顶点j到达顶点i的距离更短
if (dist[m] + graph[m][i] < dist[i]) {
// 更新源点u到顶点i的最短距离
dist[i] = dist[m] + graph[m][i];
// 更新顶点i的前驱
pre[i] = m;
}
}
}
4.代码实现
//贪心实现单源最短路径
#include
#include
int const INF = 1e7;
// N根据问题规模设定
int const N = 100;
int graph[N][N];
int dist[N];
int pre[N];
bool isIn[N] = { false };
// num表示图中顶点数量，npath表示边的数量
int num, npath;
// 打印源点u到顶点t的最短路径
void showpath(int t) {
if (pre[t] == -1) {
std::cout << t;
return;
}
showpath(pre[t]);
std::cout << "->" << t;
}
//贪心处理
void dijkstra(int u) {
// 1.初始化dist[],pre[]和isIn[]
for (int i = 1; i <= num; i++) {
dist[i] = graph[u][i];
isIn[i] = false;
if (graph[u][i] < INF)
pre[i] = u;
else
pre[i] = -1;
}
// 将源点u加入到集合S中
isIn[u] = true;
// 源点到自己的距离为0
dist[u] = 0;
// 2.找dist[]值最小的顶点并加入集合S
for (int j = 1; j <= num; j++) { // n次循环将n个顶点都加入集合S中
int temp = INF, m = u; // m为集合V-S中要找的距离源点u最近的顶点
for (int i = 1; i <= num; i++) {
if (!isIn[i] && dist[i] < temp) {
m = i;
temp = dist[i];
}
}
// 如果找不到j(flag[]全为true,顶点已经全部找完),结束
if (m == u) return;
// 如果找到，将t加入集合S
isIn[m] = true;
// 3.更新路径
for (int i = 1; i <= num; i++) {
// !isIn[i] = false表示顶点i在集合V-S中
// graph[m][i] 表示顶点i顶点m邻接(即m->i有边存在)
if (!isIn[i] && graph[m][i] < INF) {
// 经过顶点j到达顶点i的距离更短
if (dist[m] + graph[m][i] < dist[i]) {
// 更新源点u到顶点i的最短距离
dist[i] = dist[m] + graph[m][i];
// 更新顶点i的前驱
pre[i] = m;
}
}
}
}
}
int main() {
// 初始化graph
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
graph[i][j] = INF;
}
}
int start, end, distance;
std::cout << "请输入顶点总数和边数(以空格隔开):" << std::endl;
std::cin >> num >> npath;
//读入数据
std::cout << "请依次输入" << npath << "条边的起始点，终点和权值(以空格隔开):" << std::endl;
for (int i = 0; i < npath; i++) {
std::cin >> start >> end >> distance;
graph[start][end] = distance;
}
// 调用dijkstra，这里设置顶点1为源点
dijkstra(1);
for (int i = 1; i <= num; i++) {
std::cout << "源点u到顶点" << i << "的最短距离为:" << dist[i] << ", 最短路径为:";
showpath(i);
std::cout << std::endl;
}
return 0;
}
5.实验结果
请输入顶点总数和边数(以空格隔开):
5 8
请依次输入8条边的起始点，终点和权值(以空格隔开):
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
4 3 2
3 5 1
4 5 4
源点u到顶点1的最短距离为:0, 最短路径为:1
源点u到顶点2的最短距离为:2, 最短路径为:1->2
源点u到顶点3的最短距离为:4, 最短路径为:1->2->3
源点u到顶点4的最短距离为:8, 最短路径为:1->2->4
源点u到顶点5的最短距离为:5, 最短路径为:1->2->3->5
6.算法改进
diskstra中两次for循环嵌套,时间复杂度为O(n^2), 在结合V-S中寻找距离源点u最近的顶点m,其时间复杂度为O(n),如果改用优先队列，就可以把时间复杂度将为O(logn)。要想实现优先队列对顶点进行排序，就要定义新的结构体，定义排序规则等一些额外的工作。
7.代码实现(改进版)
//贪心实现单源最短路径(使用优先队列)
#include
#include
#include
#include
int const INF = 1e7;
// N根据问题规模设定
int const N = 100;
int graph[N][N];
int dist[N];
int pre[N];
bool isIn[N] = { false };
// num表示图中顶点数量，npath表示边的数量
int num, npath;
struct Node {
int id, step; // id为顶点编号,step为源点u到编号为id顶点的最短路径
// 构造函数
Node (int _target, int _step):id(_target), step(_step){}
// 设置比较规则(优先队列的比较算法greater会调用)
bool operator > (const Node& node) const {
return step > node.step;
}
};
// 打印源点u到顶点t的最短路径
void showpath(int t) {
if (pre[t] == -1) {
std::cout << t;
return;
}
showpath(pre[t]);
std::cout << "->" << t;
}
void dijkstra2(int u) {
// priority_queue 默认排序规则是less，却是从大到小排序(就是这么反人类!)
// 因此需要修改比较规则为std::greater，变成从小到大排序(这里比较特殊！)
std::priority_queue < Node, std::vector, std::greater> q;
// 1.初始化dist[],pre[]和isIn[]
for (int i = 1; i <= num; i++) {
dist[i] = INF;
pre[i] = -1;
}
q.push(Node(u, 0));
dist[u] = 0;
while (!q.empty()) {
// 2.取出当前离源点最近的顶点
Node node = q.top();
q.pop();
int m = node.id;
// 将选出的顶点加入到集合S中
isIn[m] = true;
// 3.更新路径
for (int i = 1; i <= num; i++) {
// !isIn[i] = false表示顶点i在集合V-S中
// graph[m][i] 表示顶点i顶点m邻接(即m->i有边存在)
if (!isIn[i] && graph[m][i] < INF) {
// 经过顶点j到达顶点i的距离更短
if (dist[m] + graph[m][i] < dist[i]) {
// 更新源点u到顶点i的最短距离
dist[i] = dist[m] + graph[m][i];
q.push(Node(i, dist[i]));
// 更新顶点i的前驱
pre[i] = m;
}
}
}
}
}
int main() {
//初始化graph
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
graph[i][j] = INF;
}
}
int start, end, distance;
std::cout << "请输入顶点总数和边数(以空格隔开):" << std::endl;
std::cin >> num >> npath;
//读入数据
std::cout << "请依次输入" << npath << "条边的起始点，终点和权值(以空格隔开):" << std::endl;
for (int i = 0; i < npath; i++) {
std::cin >> start >> end >> distance;
graph[start][end] = distance;
}
// 调用dijkstra
dijkstra2(1);
for (int i = 1; i <= num; i++) {
std::cout << "源点u到顶点" << i << "的最短距离为:" << dist[i] << ", 最短路径为:";
showpath(i);
std::cout << std::endl;
}
return 0;
}
8.实验结果(改进版)
请输入顶点总数和边数(以空格隔开):
5 8
请依次输入8条边的起始点，终点和权值(以空格隔开):
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
4 3 2
3 5 1
4 5 4
源点u到顶点1的最短距离为:0, 最短路径为:1
源点u到顶点2的最短距离为:2, 最短路径为:1->2
源点u到顶点3的最短距离为:4, 最短路径为:1->2->3
源点u到顶点4的最短距离为:8, 最短路径为:1->2->4
源点u到顶点5的最短距离为:5, 最短路径为:1->2->3->5
9.参考文献
1.陈小玉《趣学算法》第二章相关内容。
我是lioney，年轻的后端攻城狮一枚，爱钻研，爱技术，爱分享。
个人笔记，整理不易，感谢阅读、点赞和收藏。
文章有任何问题欢迎大家指出，也欢迎大家一起交流后端各种问题！
