最短路径(Dijkstra算法)

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

1.概念

(1)最短路径:

  • 非网图:两顶点之间经历边数最小的路径
  • 网图:两顶点之间经历的边上权值之和最短的路

2.迪杰斯特拉(Dijkstra)算法

1.思路

设置一个集合S存放已经找到最短路径的顶点,并设置一个源点,dist[]数组中存放源点距离每个顶点的最短距离,path[]数组中存放的是最短路径,基本过程可以如下描述:(下图来自懒猫老师的《数据结构》相关课程笔记)

(1)先选定一个源点编号,将选定的源点加入U,将源点距(直接)其他顶点的距离赋值给dist[]数组

最短路径(Dijkstra算法)

 (2)选出现有dist[]中的最短路径,将该路径对应的顶点加入U中;并更新源点距其他顶点的距离值(意思是可以通过新加入的点再到达其他顶点)

最短路径(Dijkstra算法)

(3)再重复(2)中步骤,直至所有顶点都加入U中

最短路径(Dijkstra算法)

(4)所有结点加入U中,结束

最短路径(Dijkstra算法)

2.数据结构

(1)图的存储结构:带权的邻接矩阵存储结构

(2)数组dist[n]:每个分量distfl表示当前所找到的从始点v到终点»的最短路径的长度。初态为:若从v到vi有弧,则disti为弧上权值;否则置distil为∞。

(3)数组path[n]:path[i]是一个字符串,表示当前所找到的从始点v到终点vi的最短路径。初态为:若从V有弧,则path[i]为0:否则置path[i]为-1。

(4)数组s[n]:存放源点和己经生成的终点,其初态为只有一个源点v

最短路径(Dijkstra算法)

3.代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX 10//最大的顶点个数
#define INT_MAX_ 100000
typedef int DataType;
int findMinDist(int *dist, int *s, int vertexNum);

void MGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum, int arcNum) { //初始化构造图(邻接矩阵法)
	printf("请逐个输入顶点的内容:");
	DataType x;
	DataType vi, vj, ave; //构建邻接矩阵时,一条边的两个结点编号
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		scanf("%d", &x);
		vertex[i] = x;
	}
	for (int i = 0; i < vertexNum; i++) //初始化邻接矩阵
		for (int j = 0; j < vertexNum; j++) {
			if (i == j)
				arc[i][j] = 0;
			else
				arc[i][j] = INT_MAX_;//赋值正无穷
		}
	int count = 1;
	for (int i = 0; i < arcNum; i++) { //依次输入每一条边
		printf("请输入第%d条边依附的两个顶点的编号(方向->)和权值:", count++);
		scanf("%d %d %d", &vi, &vj, &ave); //输入该边依附的顶点的编号
		arc[vi][vj] = ave; //赋值权值
	}
}

void Dijkstra(int arc[][MAX_VERTEX], int vertexNum, int startV, int *s, int *dist, int *path) {
	for (int i = 0; i < vertexNum; i++) {
		dist[i] = arc[startV][i]; //初始化数组dist,path
		if (dist[i] != INT_MAX_)
			path[i] = startV; //将原点设为上一条路径
		else
			path[i] = -1;
	}
	for (int i = 0; i < vertexNum; i++) {
		s[i] = 0;
	}
	arr(dist, path, vertexNum);//验证数组内容是否正确
	s[startV] = 1; //1值代表该结点已经加入了最短路径
	int num = 1;
	int min;
	while (num < vertexNum) { //当顶点数num小于图的顶点数,即不是所有顶点加入最小路径
		min = findMinDist(dist, s, vertexNum); //dist中查找s[i]为0的最小值元素
		s[min] = 1;
		//将新生成的结点加入集合s中
		for (int i = 0; i < vertexNum; i++) {
			//修改数组dist和path
			if ((s[i] == 0) && (dist[i] > dist[min] + arc[min][i])) {
				dist[i] = dist[min] + arc[min][i]; //用已经找到的最短路径修改对应的dist
				path[i] = min; //用已经找到的最短路径修改对应的path
				arr(dist, path, vertexNum);//验证数组内容是否正确
				printf("\n");
			}
		}
		num++;
	}
}

int findMinDist(int *dist, int *s, int vertexNum) {
	int flag = 0, min, index;
	for (int i = 0; i < vertexNum; i++) {
		if (flag == 0 && s[i] == 0) {
			min = dist[i];
			index = i;
			flag = 1;
		} else if (flag == 1 && s[i] == 0 && min > dist[i]) {
			min = dist[i];
			index = i;
		}
	}
	return index;
}

void displayPath(int *dist, int *path, int *s, int startV, int vertexNum) { //打印起始点到各顶点的最短路径
	int temp;
	int patharr[vertexNum];
	int con = 0;
	for (int i = 0; i < vertexNum; i++) {
		con = 0;
		if (i != startV) {
			printf("从顶点 %d --> %d:\n", startV, i);
			if (dist[i] != INT_MAX_)
				printf("最短路径长度为:%d\n", dist[i]);
			else {
				printf("不存在与该点之间的路径!\n");

				printf("\n");
				continue;
			}
			printf("最短路径为:");
			temp = i;
			while (temp != startV) { //得改成逆序的
				patharr[con++] = path[temp];
				temp = path[temp];
			}
			con--;
			if (con == 0) {
				printf("%d ->%d\n", patharr[con], i);
			} else {
				while (con >= 0) {
					printf("%d -> ", patharr[con]);
					con--;
				}
				printf("%d\n", i);
			}
			printf("\n");
		}
	}


}

void printMGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum) { //输出
	printf("vertex:");
	for (int i = 0; i < vertexNum; i++) {
		printf("%d ", vertex[i]);
	}
	printf("\n");
	printf("arc:\n");
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			if (j == vertexNum - 1) {
				if (arc[i][j] == INT_MAX_)
					printf("  *\n");
				else
					printf("  %d\n", arc[i][j]);
			} else {
				if (arc[i][j] == INT_MAX_)
					printf("  * ");
				else
					printf("  %d ", arc[i][j]);
			}
		}
	}

}

main() {
	DataType vertex[MAX_VERTEX];//储存所有的顶点
	int arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵,结点间的连通关系
	int vertexNum, arcNum; //顶点个数,边的个数
	printf("请输入顶点个数和边的个数:");
	scanf("%d %d", &vertexNum, &arcNum);
	MGraph(vertex, arc, vertexNum, arcNum);
	printf("输出邻接矩阵信息:\n");
	printMGraph(vertex, arc, vertexNum);
	int x;
	printf("请输入Dijkstra算法的起点:");
	scanf("%d", &x);
	int s[vertexNum], dist[vertexNum], path[vertexNum];
	Dijkstra(arc, vertexNum, x, s, dist, path);
	printf("\n");
	printf("逐个输出由起点 %d 到所有顶点的最短路径:\n", x);
	printf("\n");
	displayPath(dist, path, s, x, vertexNum);
}

void arr(int *dist, int *path, int vertexNum) {//验证输出数组,用来debug
	printf("检查数组内容:\n");
	for (int i = 0; i < vertexNum; i++) {
		printf("%d ", dist[i]);
	}
	printf("\n");
	for (int i = 0; i < vertexNum; i++) {
		printf("%d ", path[i]);
	}
	printf("\n");
}

4.输出测试

示例图:

最短路径(Dijkstra算法)

(两组,分别以0和1为最短路径寻找的起点)

(1)以0为起点

最短路径(Dijkstra算法)

(1)以1为起点

最短路径(Dijkstra算法)

初学小白,有错误的话欢迎指正! 文章来源地址https://www.toymoban.com/news/detail-484443.html

到了这里,关于最短路径(Dijkstra算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】单源最短路径算法——Dijkstra算法

    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。这是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用 贪心算法 的策略, 每次遍历到始点距离最

    2024年02月05日
    浏览(46)
  • Dijkstra算法求最短路

    Dijkstra算法的流程如下: 1.初始化dist[1] = 0,其余节点的dist值为无穷大。 2.找出一个未被标记的、dist[x]最小的节点x,然后标记节点x。 3.扫描节点x的所有出边(x,y,z),若dist[y] dist[x] + z,则使用dist[x] + z更新dist[y]。 4.重复上述2~3两个步骤,直到所有的节点都被标记。 Dijk

    2024年02月06日
    浏览(44)
  • 294.【华为OD机试】路口最短时间问题( Dijkstra 算法Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年03月13日
    浏览(78)
  • dijkstra模板及例题(最短路算法)

            大家好,我是永遇乐金枪鱼。图论和树论是算法中占比大且非常重要的内容,而且树论是特殊的图论,而图论中最经典的就是求解最短路,而最短路算法是比较广泛且冗杂的算法,与其相关的有较多的算法,下面我给大家讲讲常用算法之一——dijkstra算法。  📒博客

    2023年04月08日
    浏览(46)
  • 【Dijkstra】最短路算法的一种

    首先,本文默认读者基本熟悉Dijkstra基本原理 DIjkstra是单源最短路的一种算法。使用数组d[i]来储存结点i到源点s的最短路径长度,每次更新d[i]数组后,d[i]中最小的一定是一条最短路径长度。也就是说每次更新后都能找到一条最短路径,以下给出证明: 假设d[]数组中当前最小

    2024年02月03日
    浏览(55)
  • 二、搜索与图论6:Dijkstra 模板题+算法模板(Dijkstra求最短路 I, Dijkstra求最短路 II,1003 Emergency)

    朴素dijkstra算法 对应模板题:Dijkstra求最短路 I 时间复杂是 O(n^2+m):n 表示点数,m 表示边数 堆优化版dijkstra 对应模板题:Dijkstra求最短路 II 时间复杂度 O(mlogn):n 表示点数,m 表示边数 树是一种特殊的图 ,与图的存储方式相同。 对于无向图中的边ab,存储两条有向边a-b, b-a。

    2024年02月14日
    浏览(37)
  • 数据结构--最短路径 Dijkstra算法

    计算  b e g i n  点到各个点的最短路 color{red}计算 begin 点到各个点的最短路 计算   b e g in   点到各个点的最短路 如果是无向图,可以先把无向图转化成有向图 我们需要2个数组 final[] (标记各顶点是否已找到最短路径)与 dis[] (最短路径⻓度)数组 Dijkstra算法是一种用于

    2024年02月12日
    浏览(37)
  • 12.图论1 最短路之dijkstra算法

    二分图 判定:染色法。 性质: 可以二着色。 无奇圈。 树的直径模板 两遍dfs/bfs,证明时反证法的核心是用假设推出矛盾。 设1是一开始随机选的点,s是与其最远的点,证明s是直径的一端。 反证:假设s不是直径的一端,ss是直径的一端。 现在要做的就是证明ss是直径的一端

    2024年02月20日
    浏览(47)
  • 【图论算法】最短路径算法(无权最短路径、Dijkstra算法、带负边值的图、无圈图)

    本篇博客将考察各种最短路径问题。     无权最短路径     Dijkstra 算法     具有负边值的图     无圈图     所有顶点对间的最短路径     最短路径的例子–词梯游戏 输入是一个赋权图:与每条边 (v i , v j ) 相联系的是穿越该边的开销(或称为值

    2023年04月12日
    浏览(43)
  • 最短路径算法|Dijkstra‘s Algorithm

    最短路径问题几乎是每个计算机专业学生的必学知识点,相关的算法也比较多样,但其中最经典的肯定是由荷兰计算机科学家,1972年图灵奖得主Edsger Dijkstra于1959年发布的Dijkstra\\\'s Algorithm。 最短路径问题简单来说就是给定一个图和图中的一个源顶点,找到从源到给定图中所有

    2023年04月14日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包