C语言 最短路径 迪杰斯特拉(Dijkstra)算法

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

前言

基于c语言的最短路由,数据结构与算法,算法,数据结构

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


不太懂的可以看视频 QWQ  (来着@Abel)

Dijkstra算法讲解


算法实现:

  1. 定义一个数组dist[],dist[i]表示从起点到顶点i的最短路径长度,初始化为无穷大,dist[s]=0,其中s为起点。
  2. 定义一个数组visited[],visited[i]表示顶点i是否已经被标记为已确定最短路径的顶点,初始化为false。
  3. 从dist[]中找到当前未被标记的dist[i]最小的顶点u,标记visited[u]=true。
  4. 遍历所有与u相邻的顶点v,如果visited[v]=false,且从起点到u再到v的路径长度小于dist[v],则更新dist[v]=dist[u]+w(u,v),其中w(u,v)为边(u,v)的权值。

重复步骤3和步骤4,直到所有顶点都被标记为已确定最短路径的顶点。

基于c语言的最短路由,数据结构与算法,算法,数据结构

以下是求无向网(储存方式为邻接矩阵)中起点s到各点的最短路径的代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#define MVNum 100//最大顶点数
#define MaxInt 66666//表示极大值
typedef struct {
	char vexs[MVNum];//顶点表(顶点为字符型)
	int arcs[MVNum][MVNum];//邻接矩阵(权值为整型)
	int vexnum, arcnum;//图的当前点数和边数
}AMGraph;

//定位
int LocateVex(AMGraph* G, char v) {
	int i;
	for (i = 0; i < G->vexnum; i++) {
		if (G->vexs[i] == v) {
			return i;
		}
	}
	return -1;
}

//无向网的建立
AMGraph* CreateUDN() {
	int i, j, k, w;
	char v1, v2;
	AMGraph* G = malloc(sizeof(AMGraph));
	printf("输入总顶点数,边数\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	getchar();//吸收换行符
	printf("依次输入点的信息\n");
	for (i = 0; i < G->vexnum; i++) {
		scanf("%c", &G->vexs[i]);
	}
	getchar();//吸收换行符
	for (i = 0; i < G->vexnum; i++)
		for (j = 0; j < G->vexnum; j++) {
			if (i == j) {
				G->arcs[i][j] = 0;
			}
			else {
				G->arcs[i][j] = MaxInt;
			}
		}
	for (k = 0; k < G->arcnum; k++) {
		printf("输入一条边依附的顶点及权值\n");
		scanf("%c%c", &v1, &v2);
		scanf("%d", &w);
		getchar();//吸收换行符
		i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在顶点数组的下标
		G->arcs[i][j] = w;//边<v1,v2>权值置为w
		G->arcs[j][i] = w;//无向网对称边<v2,v2>权值也置为w
	}
	return G;
}

//输出邻接矩阵
void print(AMGraph* G) {
	int i, j;
	printf("  ");
	for (i = 0; i < G->vexnum; i++) {
		printf("%c ", G->vexs[i]);
	}
	printf("\n");
	for (i = 0; i < G->vexnum; i++) {
		printf("%c ", G->vexs[i]);
		for (j = 0; j < G->vexnum; j++) {
			if (G->arcs[i][j] == MaxInt)
				printf("∞ ");
			else
				printf("%d ", G->arcs[i][j]);
		}
		printf("\n");
	}
}

//迪杰斯特拉算法
void Dijkstra(AMGraph* G, int s) {
	int dist[MVNum];//用来储存各顶点与起点的距离
	bool visited[MVNum];//用来标记已确定最短路径的顶点
	int i, j, k, u, min;
	//初始化数组dist与visited
	for (i = 0; i < G->vexnum; i++) {
		dist[i] = MaxInt;
		visited[i] = false;
	}
	dist[s] = 0;//起始点s最短距离为0
	//每次循环会标记一个顶点u,直到所有顶点被标记(循环次数就是顶点数-1,起点已找到最短路径0)
	for (k = 1; k < G->vexnum; k++) {
		min = MaxInt;
		//找到当前未被标记的距离起点最近的顶点u
		for (i = 0; i < G->vexnum; i++) {
			if (dist[i] < min && !visited[i]) {
				u = i;
				min = dist[i];
			}
		}
		visited[u] = true;//标记顶点u
		/*遍历顶点u的邻结点,当 dist[u] + G->arcs[u][j] < dist[j]时
		(顶点u距离起点s的长度dist[u]加上顶点u与邻接点j的距离G->arcs[u][j]小于顶点j距离起点s的距离dist[j]),
		更新顶点j距离起点的路径长度*/
		for (j = 0; j < G->vexnum; j++) {
			if (!visited[j] && dist[u] + G->arcs[u][j] < dist[j]) {
				dist[j] = dist[u] + G->arcs[u][j];
			}
		}
	}
	//输出结果
	for (i = 0; i < G->vexnum; i++) {
		printf("起点%c到顶点%c的最短路径为:%d\n", G->vexs[s], G->vexs[i], dist[i]);
	}
}

int main() {
	AMGraph* G = CreateUDN();
	printf("该无向网邻接矩阵为:\n");
	print(G);
	Dijkstra(G, 0);
}

若顶点数为n,求解最短路径的主循环共进行n-1次,每次执行的时间为,所以算法时间复杂度为。


示例:

求如下图所示v0到各点的最短路径

基于c语言的最短路由,数据结构与算法,算法,数据结构

 运行结果如下:

A、B、C······代替v0、v1、v2······

基于c语言的最短路由,数据结构与算法,算法,数据结构


总结

如果是有向网或者是以邻接表方式储存的有权图,算法实现流程还是一样的,只不过代码上大同小异。文章来源地址https://www.toymoban.com/news/detail-770475.html

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

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

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

相关文章

  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(39)
  • 使用omp并行技术加速最短路径算法-迪杰斯特拉(Dijkstra)算法(记录最短路径和距离)

    原理: Dijkstra算法是解决**单源最短路径**问题的**贪心算法** 它先求出长度最短的一条路径,再参照该最短路径求出长度次短的一条路径     直到求出从源点到其他各个顶点的最短路径。 首先假定源点为u,顶点集合V被划分为两部分:集合 S 和 V-S。 初始时S中仅含有源点u,

    2024年02月10日
    浏览(49)
  • 数据结构与算法 —— 最短路径Dijkstra算法(迪杰斯特拉)详细图解以及python实现

    目录 前言 1. 介绍 2. 加权图 2.1 概念 3. 最短路径 -- Dijkstra 算法 3.1 历史 3.2 Dijkstra 算法的基本思路 3.3 Dijkstra 算法图解 4.  python中dijkstra算法的实现 5. 总结  前两章我们讲到了关于图的基本知识,和广度/深度优先搜索。 本章,我们将介绍 加权图 和 最短路径 的相关知识。 最

    2024年02月12日
    浏览(52)
  • 迪杰斯特拉(Dijkstra's )算法——解决带权有向无向图最短路径

    迪杰斯特拉算法(Dijkstra\\\'s Algorithm),又称为狄克斯特拉算法,是一种用于解决带权重有向图或无向图最短路径问题的算法。该算法由荷兰计算机科学家艾兹赫尔·狄克斯特拉在1956年发明,是一种广泛应用于网络路由和其他领域的算法。 在 2001 年的一次采访中,Dijkstra 博士透露

    2024年02月03日
    浏览(48)
  • 【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

    问题解答 (1)最小生成树(Minimal Spanning Tree)的定义 生成树的代价 :设 G ( V , E ) G(V,E) G ( V , E ) 是一个无向连通网图,生成树上 各边的权值之和 称为 生成树的代价 。 最小生成树 :在图 G G G 所有生成树中, 代价最小的生成树 为 最小生成树 。 (2)最小生成树(MST)的性

    2024年02月11日
    浏览(39)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(58)
  • Dijkstra(迪杰斯特拉)算法

    Dijkstra(迪杰斯特拉)算法的思想是广度优先搜索(BFS) 贪心策略。 是从一个顶点到其余各顶点的最短路径算法,节点边是不各自不同的权重,但都必须是正数 如果是负数,则需要 Bellman-Ford 算法 如果想求任意两点之间的距离,就需要用 Floyd 算法 求节点0 - 4 的最短路径 每次从

    2024年04月12日
    浏览(32)
  • 数据结构--迪杰斯特拉(Dijkstra)算法

    生活封锁了我们,只要我们的心不死,生活便永远不是一汪死水,而我们,依然会绽放最美的姿态。 戴克斯特拉算法(英语:Dijkstra’s algorithm),又称迪杰斯特拉算法、Dijkstra算法,是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法,并于3年后在期刊上发表。

    2024年02月04日
    浏览(51)
  • dijkstra迪杰斯特拉算法(邻接表法)

    算法简易过程: 求单源有向图最短路径 使用 邻接表法 来存储顶点和边,录入 有向图 。 (当然也可以无向图,不过录入时要录入两次,比如 a b 3        b a 3)  代码如下: 测试如下:  

    2024年02月07日
    浏览(42)
  • (迪杰斯特拉)Dijkstra算法及其优化(C++)

    题目描述 给定一个 n n n 个点 m m m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。 请你求出 1 1 1 号点到 n n n 号点的最短距离,如果无法从 1 1 1 号点走到 n n n 号点,则输出 − 1 −1 − 1 。 输入格式 第一行包含整数 n n n 和 m m m 。 接下来 m m m 行每行包含三

    2023年04月09日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包