devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

基于 Dijsktra(迪杰斯特拉) 算法的最短路径求值_掌握图的邻接矩阵表示法,掌握采用邻接矩阵表示法创建图的算法。 2.掌握求解最短路

作者：不正经 | 2024-06-13 05:26:12

赞

踩

掌握图的邻接矩阵表示法,掌握采用邻接矩阵表示法创建图的算法。 2.掌握求解最短路

一、实验目的

1.掌握图的邻接矩阵表示法，掌握采用邻接矩阵表示法创建图的算法。

2.掌握求解最短路径的 Dijsktra 算法。

二、实验内容

问题描述 一张地图包括 n 个城市，假设城市间有 m 条路径(有向图)，每条路径的长度 已知。给定地图的一个起点城市和终点城市，利用 Dijsktra 算法求出起点到终 点之间的最短路径。 输入要求 多组数据，每组数据有 m+3 行。第一行为两个整数 n 和 m，分别代表城市 个数 n 和路径条数 m。第二行有 n 个字符，代表每个城市的名字。第三行到第 m+2 行每行有两个字符 a 和 b 和一个整数 d，代表从城市 a 到城市 b 有一条距离 为 d 的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当 n 和 m 都等于 0 时，输入结束。 输出要求 每组数据输出 2 行。第 1 行为一个整数，为从起点到终点之间最短路的长度。 第 2 行为一串字符串，代表该路径。每两个字符之间用空格隔开。 

输入样例

3 3 //三条城市三条边 

A B C// 城市的名称

A B 1// 边和权重

B C 1

C A 3

A C// 所求AC最短距离

输出样例

2// 最短路的长度

A B C// 路径

Dijkstra算法的时间复杂度取决于实现方式，但通常是O(V^2)或O((V + E) * log(V))，其中V是顶点数，E是边数。在使用最小堆（优先队列）等数据结构进行优化时，算法的时间复杂度可以降低。

假设读者已了解算法具体过程,下面给出实现代码

1. 图的邻接矩阵存储表示：

  1. #define MVNum 100
  2. #define MaxInt 32767
  3.  
  4. typedef struct {
  5.     char vex[MVNum];        // 顶点表
  6.     int arcs[MVNum][MVNum]; // 邻接矩阵，权重为整数
  7.     int Vexnum;             // 顶点数
  8.     int arcnum;             // 边数
  9. } AMGraph;

2.对G进行初始化

  1. void initG(AMGraph& G, int n) {
  2.     int Max = numeric_limits<int>::max();// 取较大值代替无穷
  3.     
  4.     // 对邻接矩阵进行初始化
  5.     for (int i = 0; i < n; i++) {
  6.         for (int j = 0; j < n; j++) {
  7.             G.arcs[i][j] = Max;
  8.         }
  9.     }
  10. }

3.对G进行输入

  1. void inputG(AMGraph& G, int n, int m) {
  2.     // 对城市进行录入
  3.     for (int i = 0; i < n; i++) {
  4.         cin >> G.vex[i];
  5.     }
  6.  
  7.     initG(G, n);
  8.  
  9.     // 输入路径信息
  10.     for (int i = 0; i < m; i++) {
  11.         char a, b;
  12.         int d;
  13.         cin >> a >> b >> d;
  14.         int index_a = find(G.vex, G.vex + n, a) - G.vex;// G.vex为起始位置,迭代器获取a的索引
  15.         int index_b = find(G.vex, G.vex + n, b) - G.vex;// G.vex为起始位置,迭代器获取b的索引
  16.         G.arcs[index_a][index_b] = d;
  17.     }
  18.  
  19.  
  20. }

3.Dijsktra代码实现过程

  1. void Dijkstra(AMGraph G, int start, int end, int& minDist, vector<int>& path) {
  2.     int Max = numeric_limits<int>::max();// 取较大值代替无穷
  3.     
  4.     vector<int> dist(G.Vexnum, Max); // 用于存储起点到各顶点的最短距离
  5.     vector<bool> visited(G.Vexnum, false); // 记录顶点是否已访问
  6.     vector<int> Path(G.Vexnum, -1); // 记录路径上的前驱节点
  7.  
  8.     dist[start] = 0;// 起点到起点的距离设为零
  9.  
  10.     for (int i = 0; i < G.Vexnum; ++i) {
  11.         int minIndex = -1;// 当前阶段找到的最小距离的顶点的索引
  12.         int minDistance = Max;// 最小的距离,初始化为无穷
  13.  
  14.         // 选取未访问的顶点中距离最小的顶点
  15.         for (int j = 0; j < G.Vexnum; ++j) {
  16.             if (!visited[j] && dist[j] < minDistance) {
  17.                 minIndex = j;
  18.                 minDistance = dist[j];
  19.             }
  20.         }
  21.  
  22.         if (minIndex == -1) {
  23.             break; // 所有顶点都被访问过
  24.         }
  25.  
  26.         visited[minIndex] = true;// 将当前已经访问的节点置为true
  27.  
  28.         // 更新与选取顶点相邻的顶点的最短距离
  29.         for (int k = 0; k < G.Vexnum; ++k) {
  30.             // 如果顶点 k 未被访问且存在从当前顶点 minIndex 到顶点 k 的边
  31.             if (!visited[k] && G.arcs[minIndex][k] < Max) {
  32.                 int newDist = dist[minIndex] + G.arcs[minIndex][k];// 计算从起点经过 minIndex 到达顶点 k 的新路径长度
  33.                 if (newDist < dist[k]) {
  34.                     dist[k] = newDist;  // 更新起点到顶点 k 的最短路径长度
  35.                     Path[k] = minIndex;  // 记录顶点 k 在最短路径上的前驱顶点为 minIndex
  36.                 }
  37.             }    
  38.         }
  39.     }
  40.  
  41.     minDist = dist[end];// 记录从起点到终点的最短路径长度
  42.     int vi = end;// vi 为终点 end 在顶点表 vex[] 中的索引
  43.     
  44.     // 从终点开始反向遍历最短路径上的各个顶点
  45.     while (vi != -1) {
  46.         path.push_back(vi);// 将当前顶点 vi 添加到路径中
  47.         vi = Path[vi];  // 获取当前顶点 vi 在最短路径上的前驱顶点的索引
  48.     }
  49.     reverse(path.begin(), path.end()); // 反转路径，使起点到终点的顺序正确
  50. }

完整代码实现

  1. #include <iostream>
  2. #include <climits>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. #define MVNum 100
  9. #define MaxInt 32767
  10.  
  11. typedef struct {
  12.     char vex[MVNum];        // 顶点表
  13.     int arcs[MVNum][MVNum]; // 邻接矩阵，权重为整数
  14.     int Vexnum;             // 顶点数
  15.     int arcnum;             // 边数
  16. } AMGraph;
  17.  
  18. // 对G进行初始化
  19. void initG(AMGraph& G, int n) {
  20.     int Max = numeric_limits<int>::max();// 取较大值代替无穷
  21.     
  22.     // 对邻接矩阵进行初始化
  23.     for (int i = 0; i < n; i++) {
  24.         for (int j = 0; j < n; j++) {
  25.             G.arcs[i][j] = Max;
  26.         }
  27.     }
  28. }
  29.  
  30. // 对G进行输入
  31. void inputG(AMGraph& G, int n, int m) {
  32.     // 对城市进行录入
  33.     for (int i = 0; i < n; i++) {
  34.         cin >> G.vex[i];
  35.     }
  36.  
  37.     initG(G, n);
  38.  
  39.     // 输入路径信息
  40.     for (int i = 0; i < m; i++) {
  41.         char a, b;
  42.         int d;
  43.         cin >> a >> b >> d;
  44.         int index_a = find(G.vex, G.vex + n, a) - G.vex;// G.vex为起始位置,迭代器获取a的索引
  45.         int index_b = find(G.vex, G.vex + n, b) - G.vex;// G.vex为起始位置,迭代器获取b的索引
  46.         G.arcs[index_a][index_b] = d;
  47.     }
  48.  
  49.  
  50. }
  51.  
  52. void Dijkstra(AMGraph G, int start, int end, int& minDist, vector<int>& path) {
  53.     int Max = numeric_limits<int>::max();// 取较大值代替无穷
  54.     
  55.     vector<int> dist(G.Vexnum, Max); // 用于存储起点到各顶点的最短距离
  56.     vector<bool> visited(G.Vexnum, false); // 记录顶点是否已访问
  57.     vector<int> Path(G.Vexnum, -1); // 记录路径上的前驱节点
  58.  
  59.     dist[start] = 0;// 起点到起点的距离设为零
  60.  
  61.     for (int i = 0; i < G.Vexnum; ++i) {
  62.         int minIndex = -1;// 当前阶段找到的最小距离的顶点的索引
  63.         int minDistance = Max;// 最小的距离,初始化为无穷
  64.  
  65.         // 选取未访问的顶点中距离最小的顶点
  66.         for (int j = 0; j < G.Vexnum; ++j) {
  67.             if (!visited[j] && dist[j] < minDistance) {
  68.                 minIndex = j;
  69.                 minDistance = dist[j];
  70.             }
  71.         }
  72.  
  73.         if (minIndex == -1) {
  74.             break; // 所有顶点都被访问过
  75.         }
  76.  
  77.         visited[minIndex] = true;// 将当前已经访问的节点置为true
  78.  
  79.         // 更新与选取顶点相邻的顶点的最短距离
  80.         for (int k = 0; k < G.Vexnum; ++k) {
  81.             // 如果顶点 k 未被访问且存在从当前顶点 minIndex 到顶点 k 的边
  82.             if (!visited[k] && G.arcs[minIndex][k] < Max) {
  83.                 int newDist = dist[minIndex] + G.arcs[minIndex][k];// 计算从起点经过 minIndex 到达顶点 k 的新路径长度
  84.                 if (newDist < dist[k]) {
  85.                     dist[k] = newDist;  // 更新起点到顶点 k 的最短路径长度
  86.                     Path[k] = minIndex;  // 记录顶点 k 在最短路径上的前驱顶点为 minIndex
  87.                 }
  88.             }    
  89.         }
  90.     }
  91.  
  92.     minDist = dist[end];// 记录从起点到终点的最短路径长度
  93.     int vi = end;// vi 为终点 end 在顶点表 vex[] 中的索引
  94.     
  95.     // 从终点开始反向遍历最短路径上的各个顶点
  96.     while (vi != -1) {
  97.         path.push_back(vi);// 将当前顶点 vi 添加到路径中
  98.         vi = Path[vi];  // 获取当前顶点 vi 在最短路径上的前驱顶点的索引
  99.     }
  100.     reverse(path.begin(), path.end()); // 反转路径，使起点到终点的顺序正确
  101. }
  102.  
  103.  
  104.  
  105. int main() {
  106.     int n;// 城市的个数
  107.     int edge;// 有向边
  108.     cin >> n >> edge;
  109.  
  110.     AMGraph G;// 创建图G
  111.     // 图G参数赋值
  112.     G.Vexnum = n;
  113.     G.arcnum = edge;
  114.  
  115.     inputG(G, n, edge);
  116.  
  117.     char start;// 起始目标节点
  118.     char end;// 终止目标节点
  119.     cin >> start >> end;
  120.  
  121.     int minDist;// 存储目标结点间最短路径
  122.     vector<int> path;// 存储从起点到终点的最短路径上的顶点序列
  123.     int startIndex = find(G.vex, G.vex + n, start) - G.vex;// 迭代器,计算start索引
  124.     int endIndex = find(G.vex, G.vex + n, end) - G.vex;// 迭代器, 计算end索引
  125.  
  126.     Dijkstra(G, startIndex, endIndex, minDist, path);
  127.  
  128.     // 输出结果
  129.     cout << minDist << endl;
  130.     for (int i = 0; i < path.size(); ++i) {
  131.         cout << G.vex[path[i]];
  132.         if (i < path.size() - 1) {
  133.             cout << " ";
  134.         }
  135.     }
  136.     cout << endl;
  137.  
  138.     return 0;
  139. }
  140.

运行结果

输入为

  1. 3 3
  2. A B C
  3. A B 1
  4. B C 1
  5. C A 3
  6. A C

输出

  1. 2
  2. A B C

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/711064
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号