一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com
Last edited: 2022.12.3
目录
一、实验目的
二、实验设备
三、实验内容
【问题描述】
【输入要求】
【输出要求】
【输入样例】
【输出样例】
四、实验提示
五、实验步骤
5.1
六、实验结果
6.1程序完成后关键源码及运行结果截图
七、实验总结
八：划重点参考代码
作者有言
| 课程名称： | 数据结构 |
| 项目名称： | 基于Dijsktra算法的最短路径求解 |
| 实验类型： | 设计性实验 |
一、实验目的
1.掌握图的邻接矩阵表示法，掌握采用邻接矩阵表示法创建图的算法。
2.掌握求解最短路径的Dijsktra算法。
二、实验设备
装有Dev C++的计算机一台
三、实验内容
结合在头歌上已完成的实训任务进行填写，不限于下方要求。可自行补充算法分析、算法描述或流程图
【问题描述】
一张地图包括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
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
D E 20
E F 60
D F 10
A F
0 0
【输出样例】
2
A B C
60
A E D F
四、实验提示
此实验内容即为主教材算法6.10的扩展内容，算法6.10求出源点v0到图中其余所有顶点的最短路径。本实验要求求出一个指定起点到一个指定终点的最短路径。为了提高算法的效率，在求解时，可以加以判断，当已求得的终点为指定终点时，则可以终止求解，按要求输出相应结果。
五、实验步骤
5.1
此部分可包含解题思路、最初填写的但没有通过的程序，通过调试如何找到问题并做出改正，可粘贴调整规范的截图或可视化效果
六、实验结果
6.1程序完成后关键源码及运行结果截图
可以将最终完成的代码、运行结果或可视化效果在此展示。
七、实验总结
用简介、准确的语言描述本次实验重点解决了什么问题，学习了什么知识，自己掌握的如何等等
八：划重点参考代码
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
//#define YES cout << "YES" << endl
//#define NO cout << "NO" << endl
#define MAXLEN 20
#define INFINE 99999
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const int N = 100;
int n, m;
typedef struct ArcNode //定义结构体
{
int adjvex;//邻接顶点下标
int weight;//边的权值
struct ArcNode *next; //指向下一个邻边节点指针
}ArcNode;
typedef struct
{
char vertex;//顶点标志
ArcNode *firstedge;//保存第一个边节点指针
}VertexNode;
typedef struct
{
VertexNode adjlist[MAXLEN];//顶点数组
int vexnum; //顶点数
int arcnum; //边数
}AdjList;
//创建邻接表
AdjList *Created_Graph(AdjList *G)
{
int i, k, weight;
ArcNode *s;
char vex1, vex2; //顶点标志
int n1, n2;//顶点下标
G -> vexnum = n, G -> arcnum = m;
for (i = 1; i <= G -> vexnum; i++)
{
cin >> G -> adjlist[i].vertex;
G->adjlist[i].firstedge = NULL; //头节点指向为空;
}
for (k = 1; k <= G -> arcnum; k ++)
{
cin >> vex1 >> vex2;
for (i = 1; i <= G -> vexnum; i ++)
{
if (G -> adjlist[i].vertex == vex1) n1 = i;
if (G -> adjlist[i].vertex == vex2) n2 = i;
}
cin >> weight;
s = new(ArcNode);
s -> adjvex = n2, s -> weight = weight;
s -> next = G -> adjlist[n1].firstedge;
G -> adjlist[n1].firstedge = s;
}
return G;
}
//获取位置
int getPosition(AdjList *G, char c)
{
int m;
for (m = 1; m <= G -> vexnum; m ++)
if (G -> adjlist[m].vertex == c)
return m;
return 1;
}
//获取G中边<start, end>的权值；若start和end不是连通的，则返回无穷大。
int get_weight(AdjList *G, int start, int end)
{
ArcNode *node;
if (start == end)
return 0;
node = G -> adjlist[start].firstedge;
while (node != NULL)
{
if (end == node -> adjvex)
return node -> weight;
node = node -> next;
}
return INFINE;
}
/*
* 迪杰斯特拉算法求最短路径。统计图(G)中"顶点vs"到其它各个顶点的最短路径。
* 参数说明：
* G -- 邻接图
* vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
* prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
* dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
void Dijkstra(AdjList *G, int vs, int prev[], int dist[], char over)
{
int i, j, k, t,m;
int min;
int tmp;
int flag[INFINE]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
int path[MAXLEN][MAXLEN]={0};
// 初始化
for (i = 1; i <= G->vexnum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = get_weight(G, vs, i); // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
path[i][0] = 0;
}
// 对"顶点vs"自身进行初始化
flag[vs] = 1;
dist[vs] = 0;
path[vs][0] =1;
// 遍历G->vexnum-1次；每次找出一个顶点的最短路径。
for (i = 2; i <= G->vexnum; i++)
{
// 寻找当前最小的路径，即在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
t = 0;
min = INFINE;
for (j = 1; j <= G->vexnum; j++)
if (flag[j] == 0 && dist[j]<min)
min = dist[j], k = j;
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点，即当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 1; j <= G->vexnum; j++)
{
tmp = get_weight(G, k, j);
tmp = (tmp == INFINE ? INFINE : (min + tmp)); // 防止溢出
if (flag[j] == 0 && (tmp < dist[j]))
{
dist[j] = tmp;
prev[j] = k;
path[j][t] = k;
t++;
}
}
}
// 打印dijkstra最短路径的结果
for (i = 1; i <= G -> vexnum; i++)
{
if(G -> adjlist[i].vertex == over)
{
cout << G -> adjlist[vs].vertex << "到" << over << "的最短路径长度为:" << dist[i];
int showpath[MAXLEN] = {0};//存储最短路径上的节点
for (m = 0; m < G->vexnum; m++)
{
if (path[i][m] == 0|| G->adjlist[path[i][m]].vertex == G->adjlist[vs].vertex) break;
showpath[m] = path[i][m];
}
// //以下用于拼接路径
if (dist[i]!= INFINE)
{
cout << endl << "当前最短路径为:" << G->adjlist[vs].vertex << "->";
for (int q = MAXLEN - 1; q >= 0; q--)//存入的中间节点是【距离原点最远的顶点】依次递减存入的，故需逆序输出
{
if (showpath[q] == 0) continue;
cout << G -> adjlist[showpath[q]].vertex << "->";
}
cout << G -> adjlist[i].vertex << endl;
}
}
}
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
AdjList G;
char start1, over1;
int ps;
int dist[MAXLEN], prev[MAXLEN];
AdjList *G2 = Created_Graph(&G);//创建表
cin >> start1 >> over1;
ps = getPosition(G2, start1);//获取起点位置
Dijkstra(G2, ps, prev, dist, over1);
}
return 0;
}
作者有言
如果需要代码，请私聊博主，博主看见回。
如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……
文章出处登录后可见！
