目录😋
任务描述
本关任务：编写一个程序，利用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
开始你的任务吧，祝你成功！
通关代码
// 无穷大 // 顶点数 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; else prev[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; }
测试结果
