【C++数据结构——图】最短路径（头歌教学实验平台习题）【合集】

目录😋

任务描述

本关任务：编写一个程序，利用Dijkstra算法，实现带权有向图的最短路径。

相关知识

为了完成本关任务，你需要掌握：

带权有向图
Dijkstra算法

带权有向图

该图对应的二维数组如下所示：

int A[MAXV][MAXV]={
{0,5,INF,7,INF,INF},
{INF,0,4,INF,INF,INF},
{8,INF,0,INF,INF,9},
{INF,INF,5,0,INF,6},
{INF,INF,INF,5,0,INF},
{3,INF,INF,INF,1,0}};

Dijkstra算法

Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。
Dijkstra算法的具体步骤如下：

   1. 数据结构准备

带权有向图：使用邻接矩阵或者邻接表来存储带权有向图。例如，使用邻接矩阵A[MAXV][MAXV]来表示图，其中A[i][j]表示从顶点i到顶点j的边的权值，如果没有边则A[i][j] = INF（无穷大）。
距离数组：使用dist[MAXV]来记录从源点到各个顶点的当前最短距离。初始时，dist[v] = 0（v是源点），对于其他顶点u，如果v与u有边<v, u>，则dist[u] = A[v][u]，否则dist[u] = INF。
集合 S 和 U：可以使用布尔数组来表示集合S和U。S[i]为true表示顶点i在集合S中，S[i]为false表示顶点i在集合U中。初始时，S[v] = true，对于其他顶点i，S[i] = false。

   2. 算法执行过程

初始化

设源点为v，将dist[v]设为0，表示从源点到自身的距离为0。
对于其他顶点u，如果存在边<v, u>，则dist[u]=A[v][u]，否则dist[u]=INF。
将源点v放入集合S，其余顶点放入集合U。

迭代选择顶点

每次从集合U中选择一个距离源点v最近的顶点k。即找到k使得dist[k]在所有u∈U中最小。
将顶点k从集合U中移除，并加入到集合S中。

更新距离

对于集合U中的每个顶点u，检查是否通过顶点k可以得到更短的路径到u。
计算通过顶点k到顶点u的路径长度new_dist = dist[k]+A[k][u]。
如果new_dist < dist[u]，则更新dist[u] = new_dist。

重复直到完成

重复上述选择顶点和更新距离的步骤，直到集合U为空，即所有顶点都被加入到集合S中。

   3. 示例

假设我们有一个带权有向图，用邻接矩阵A表示：
  A = {{0, 5, INF, 7, INF, INF},{INF, 0, 4, INF, INF, INF},{8, INF, 0, INF, INF, 9},{INF, INF, 5, 0, INF, 6},{INF, INF, INF, 5, 0, INF},{3, INF, INF, INF, 1, 0}}
设源点 v = 0

初始化
dist = [0, 5, INF, 7, INF, INF]
S = [true, false, false, false, false, false]
U = [false, true, true, true, true, true]

第一轮
从U中选择距离最小的顶点，k = 1（dist[1] = 5最小）
将k = 1加入S，S = [true, true, false, false, false, false]，U = [false, false, true, true, true, true]
更新距离：
对于u = 2，new_dist = dist[1]+A[1][2]=5 + 4=9，9 > dist[2]（dist[2]初始为INF），不更新。
对于u = 3，new_dist = dist[1]+A[1][3]=5+ INF = INF，不更新。
对于u = 4，new_dist = dist[1]+A[1][4]=5+ INF = INF，不更新。
对于u = 5，new_dist = dist[1]+A[1][5]=5+ INF = INF，不更新。

第二轮
从U中选择距离最小的顶点，k = 3（dist[3] = 7最小）
将k = 3加入S，S = [true, true, false, true, false, false]，U = [false, false, true, false, true, true]
更新距离：
对于u = 2，new_dist = dist[3]+A[3][2]=7+5 = 12，12 > dist[2]（dist[2]初始为INF），不更新。
对于u = 5，new_dist = dist[3]+A[3][5]=7 + 6=13，13 > dist[5]（dist[5]初始为INF），不更新。

继续重复上述步骤，直到所有顶点都在S中。

4. 时间复杂度

如果使用邻接矩阵来存储图，Dijkstra 算法的时间复杂度为，其中V是图中顶点的数量。因为每次选择最小距离顶点需要遍历所有不在S中的顶点，一共需要V次这样的选择，每次选择后更新距离也需要遍历V个顶点。
如果使用优先队列（如二叉堆）来优化选择最小距离顶点的过程，时间复杂度可以优化到，其中E是图中边的数量。

测试说明

平台会对你编写的代码进行测试：

测试输入：

0

预期输出：
Dijkstra算法求解结果:
从顶点0到顶点1的路径长度为:5 路径为:0,1
从顶点0到顶点2的路径长度为:9 路径为:0,1,2
从顶点0到顶点3的路径长度为:7 路径为:0,3
从顶点0到顶点4的路径长度为:14 路径为:0,3,5,4
从顶点0到顶点5的路径长度为:13 路径为:0,3,5

开始你的任务吧，祝你成功！

通关代码

#include <stdio.h>#define M 65535 // 无穷大
#define N 6     // 顶点数void Dijkstra(int Cost[][N], int v0, int Distance[], int prev[]) {int s[N];int mindis, dis;int i, j, u;// 初始化for (i = 0; i < N; i++) {Distance[i] = Cost[v0][i];s[i] = 0;if (Distance[i] == M)prev[i] = -1;elseprev[i] = v0;}Distance[v0] = 0;s[v0] = 1; // 标记v0// 寻找最短路径for (i = 1; i < N; i++) {mindis = M;u = v0;for (j = 0; j < N; j++) // 求离出发点最近的顶点if (s[j] == 0 && Distance[j] < mindis) {mindis = Distance[j];u = j;}s[u] = 1;for (j = 0; j < N; j++) // 修改递增路径序列if (s[j] == 0 && Cost[u][j] < M) {dis = Distance[u] + Cost[u][j];if (Distance[j] > dis) {Distance[j] = dis;prev[j] = u;}}}
}void PrintPath(int prev[], int v0, int vn) {if (vn == v0) {printf("%d", v0);return;}PrintPath(prev, v0, prev[vn]);printf("->%d", vn);
}int main() {int Cost[N][N] = {{0, 5, M, 7, M, M},{M, 0, 4, M, M, M},{8, M, 0, M, M, 9},{M, M, 5, 0, M, 6},{M, M, M, 5, 0, M},{3, M, M, M, 1, 0}};int Distance[N];int prev[N];int v0;// 读取源点scanf("%d", &v0);// 调用Dijkstra算法Dijkstra(Cost, v0, Distance, prev);// 打印结果printf("Dijkstra算法求解结果:\n");for (int i = 0; i < N; i++) {if (i != v0) {printf("从顶点%d到顶点%d的路径长度为:%d 路径为:", v0, i, Distance[i]);PrintPath(prev, v0, i);printf("\n");}}return 0;
}