首页 > 编程语言 >Dijkstra 最短路径算法

Dijkstra 最短路径算法

时间:2024-12-13 14:56:45浏览次数:7  
标签:P0 路径 算法 最短 Dijkstra 节点

此篇文章在2023年9月28日被记录
Dijkstra算法的核心点是贪心算法:不断寻找最短的点,在最短的点上更新最短路径

1.前言

想要了解学习Dijkstra算法,需要先了解无向图与权重图,无向图顾名思义就是没有方向的图,下面表示了有向图和无向图以及权重图

img

img

2.什么是Dijkstra算法

Dijkstra 算法,可以寻找图中节点之间的最短路径。特别是,可以在图中寻找一个节点(称为“源节点”)到所有其它节点的最短路径,生成一个最短路径树。荷兰杰出计算机科学家、软件工程师 Dr.Edsger W.Dijkstra创建并发布了这个算法。
Dijkstra 算法的基础知识:

  • Dijkstra 算法从指定的节点(源节点)出发,寻找它与图中所有其它节点之间的最短路径
  • Dijkstra 算法会记录当前已知的最短路径,并在寻找到更短的路径时更新
  • 一旦找到源节点与其他节点之间的最短路径,那个节点会被标记为“已访问”并添加到路径中
  • 重复寻找过程,直到图中所有节点都已经添加到路径中。这样,就可以得到从源节点出发访问所有其他节点的最短路径方案

3.实现原理

假设存在这样一个无向图,求P0点到其他点的最短距离

img

3.1 P0为起点

img

3.2 P1为起点

img

3.3 P3为起点

img

3.4 P4为起点

img

3.5 P6为起点

img

最终得到了P0到其他各个点的最短距离:
P0(0),P1(2),P2(6),P3(7),P4(17),P5(22),P6(19)

引用链接:

【1】图文详解 Dijkstra 最短路径算法

【2】最短路径算法-迪杰斯特拉(Dijkstra)算法

标签:P0,路径,算法,最短,Dijkstra,节点
From: https://www.cnblogs.com/shumei52/p/18604935

相关文章

  • 三种基本常见的排序算法(冒泡,选择,插入)
    一: 冒泡算法是一种简单的排序算法,以下是关于它的详细介绍: 基本原理: 重复遍历要排序的数列,每次比较相邻的两个元素,如果它们的顺序错误就将它们交换过来,直到整个数列都有序为止。 算法步骤 1: 比较相邻的元素。如果第一个比第二个大,就交换它们两个。2.:对每一......
  • 【数据结构与算法图解】学习笔记(第一章)①:分析数组操作过程中的时间复杂度
    文章目录前言一、第一章:数据结构为何重要1.概念(步数,时间复杂度)【第一个理论】:书中的第一个重要理论:操作的速度,并不按时间计算,而是按`步数`计算。2,了解数组2.1通过(读取,查找,插入,删除)来分析2.1.1读取(看任意索引上的值)2.1.2查找(看数组/列表中有没有该值)2.1.3插入(往......
  • 离线算法
    整体二分简介整体二分是一种离线算法,适用于符合以下特征的DS题。询问具有可二分性。修改之间互不影响。修改无关答案判定标准。(注意是判定标准而不是判定过程)贡献满足交换律,结合律,可加性。(即答案与操作先后顺序无关,且可加)允许离线。(废话这是离线算法不允许离线还玩毛线......
  • 课程设计/单源最短路径问题的求解
    一、问题分析    问题描述:给定一个带权有向图G=(V,E),其中每条边的权是一个实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和,这个问题通常称为单源最短路径问题。该问题的经典求解方法为迪克斯特......
  • 排产算法的分类、特点和适用场景分析
    ​ 基于规则或基于约束或基于优化的排产算法在生产管理中扮演着重要角色,它们各自具有不同的特点和适用场景。以下是对这些排产算法的详细归纳。1、基于规则的排产算法算法设计​ 基于规则的排产算法是依据一系列预定义的生产规则来进行排产的。这些规则通常根据企业的生产......
  • 举例说明学习数据结构和算法有什么用?
    前端开发中,虽然不像后端开发那样频繁地处理海量数据和复杂算法,但数据结构和算法的知识仍然非常重要,它能帮助你写出更高效、更优雅的代码,提升用户体验。以下是一些前端开发中数据结构和算法的应用场景示例:1.数组和链表操作:场景:虚拟列表/无限滚动。当需要展示成千上万条数据......
  • C++实现希尔排序算法
    指定格式输入字母(字母间以空格分隔),按照希尔排序输出指定格式#include<iostream>#include<vector>#include<string>usingnamespacestd;voidshellSort(vector<string>&arr){ intn=arr.size(); //初始步长设置为数组长度的一半,后面逐步缩小步长直到值为1为止 for......
  • java雪花算法
    雪花算法适用于高并发、分布式系统中生成唯一标识符。通过合理的位数设计,确保了ID的唯一性和有序性,非常适合需要快速生成唯一ID的场景。雪花算法是一种分布式唯一ID生成算法,由Twitter开发。它生成的ID是64位的整数,具有时间排序的特性。其结构如下:```|1bit|41bits......
  • python雪花算法
    雪花算法(SnowflakeAlgorithm)是一种用于生成唯一的ID的算法,它由Twitter开发。其生成的ID在全局范围内是唯一的,适合高并发场景。雪花算法生成的ID通常是一个64位的整数,包含多个部分,具体结构如下:1.**时间戳(41位)**:当前时间的毫秒数,能支持69年的时间范围。2.**工作机器ID(10位)**:机器......
  • 《算法导论》英文版前言第2段研习录:人人都得来点算法!
    【英文版】Therefore,itbehoovesyoutounderstandalgorithmsnotjustasastudentorpractitionerofcomputerscience,butasacitizenoftheworld.Onceyouunderstandalgorithms,youcaneducateothersaboutwhatalgorithmsare,howtheyoperate,and......