实验报告——基于Dijsktra算法的最短路径求解-Toy模板网

这篇具有很好参考价值的文章主要介绍了实验报告——基于Dijsktra算法的最短路径求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com
Last edited: 2022.12.3

文章来源地址https://www.toymoban.com/news/detail-465909.html

一、实验目的

二、实验设备

三、实验内容

【问题描述】

【输入要求】

【输出要求】

【输入样例】

【输出样例】

四、实验提示

五、实验步骤

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;
}