【最短路径算法】一文掌握Dijkstra算法,详解与应用示例+代码

目录

1 Dijkstra算法

2 Dijkstra算法的步骤

3 Dijkstra算法python实现

4 Dijkstra算法应用示例详解


1 Dijkstra算法

        Dijkstra算法(迪杰斯特拉算法)是一种用于在加权图中查找从一个起始节点到所有其他节点的最短路径的算法。该算法最初由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。Dijkstra算法适用于带有非负权重的有向图或无向图。

特点和限制:

  • Dijkstra算法仅适用于非负权重的图,因为它依赖于贪婪策略来选择当前最短路径。
  • 它可以找到从起始节点到所有其他节点的最短路径,因此适用于单源最短路径问题。
  • Dijkstra算法不会处理负权边,如果图中存在负权边,应该使用其他算法,如Bellman-Ford算法。
  • 算法的时间复杂度取决于数据结构的选择,一般情况下是O(V^2)或O(Vlog(V)),其中V是节点数。如果使用优先队列来优化,时间复杂度可以减小到O(Elog(V)),其中E是边数。

        Dijkstra算法在许多领域广泛应用,包括路线规划、网络路由、资源分配和许多其他需要找到最短路径的应用。

2 Dijkstra算法的步骤

  1. 创建一个空的最短路径字典,其中每个节点的距离设置为无穷大,起始节点的距离设置为0。

  2. 创建一个空的已访问节点集合。

  3. 从未访问的节点中选择距离起始节点最近的节点,标记为已访问。

  4. 对于已访问节点的所有邻居,计算通过已访问节点到达它们的距离,并更新最短路径字典。

  5. 重复步骤3和4,直到所有节点都被访问。

3 Dijkstra算法python实现

以下是Python中使用Dijkstra算法实现的示例代码,用于查找从起始节点到其他节点的最短路径:

import heapqdef dijkstra(graph, start):# 创建一个距离字典,用于存储每个节点到起始节点的距离distances = {node: float('inf') for node in graph}distances[start] = 0# 创建一个优先队列,以便选择下一个节点priority_queue = [(0, start)]while priority_queue:current_distance, current_node = heapq.heappop(priority_queue)# 如果当前距离大于已知距离,跳过if current_distance > distances[current_node]:continue# 遍历当前节点的邻居for neighbor, weight in graph[current_node].items():distance = current_distance + weight# 如果发现更短的路径,更新距离字典和优先队列if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(priority_queue, (distance, neighbor))return distances# 创建一个示例图
graph = {'A': {'B': 2, 'D': 1},'B': {'A': 2, 'C': 3, 'E': 2},'C': {},'D': {'E': 1},'E': {}
}# 起始节点
start_node = 'A'# 调用Dijkstra算法函数
shortest_distances = dijkstra(graph, start_node)# 打印最短路径和距离
for node, distance in shortest_distances.items():print(f'Shortest distance from {start_node} to {node} is {distance}')

运行: 

        这段代码定义了一个 dijkstra 函数,用于执行Dijkstra算法。它接受一个图的表示和起始节点作为参数,并返回一个包含从起始节点到其他节点的最短路径的字典。然后,我们创建一个示例图,并使用Dijkstra算法找到从节点 A 到其他节点的最短路径。

        请注意,你可以根据你的需求更改示例图和起始节点,以便应用Dijkstra算法到你的具体问题中。

4 Dijkstra算法应用示例详解

假设我们有以下有向图:

在这个示意图中,有向图包括节点 A、B、C、D 和 E,以及它们之间的带权重的边。边的数字表示权重或距离。我们的目标是找到从节点 A 到其他节点的最短路径。

Dijkstra算法的执行步骤:

  1. 初始化:开始时,我们选择节点 A 作为起始节点,并将其距离设置为 0。同时,将其他节点的距离初始化为无穷大,表示尚未知道到达它们的最短路径。

  2. 选择下一个节点:首先,我们选择节点 A 作为当前节点。它是起始节点,距离已知。

  3. 更新距离:我们计算从节点 A 到其邻居节点 B 和 C 的距离,并将这些距离记录下来。当前已知的最短距离是从 A 到 B 的距离为 4,从 A 到 C 的距离为 2。

  4. 选择下一个节点:现在,我们选择距离最短的节点 C 作为当前节点。

  5. 更新距离:我们计算从 A 经过 C 到达其邻居节点 B 和 D 的距离,并将这些距离记录下来。距离从 A 经过 C 到 B 的距离变为 4 + 5 = 9,从 A 经过 C 到 D 的距离变为 2 + 5 = 7。

  6. 选择下一个节点:然后,我们选择距离最短的节点 B 作为当前节点。

  7. 更新距离:我们计算从 A 经过 B 到达其邻居节点 D 的距离,并将这个距离记录下来。距离从 A 经过 B 到 D 的距离变为 4 + 5 + 3 = 12。

  8. 选择下一个节点:最后,我们选择距离最短的节点 D 作为当前节点。

  9. 更新距离:我们计算从 A 经过 D 到达其邻居节点 E 的距离,并将这个距离记录下来。距离从 A 经过 D 到 E 的距离变为 4 + 5 + 3 + 7 = 19。

  10. 完成:所有节点都已被访问,算法结束。

以上最短路径从节点 A 到其他节点的距离如下: 

  • A到A是 0
  • A到B是 9
  • A到C是 2
  • A到D是 12
  • A到E是 19

        这个示意图展示了Dijkstra算法是如何逐步找到最短路径,并在每一步中选择距离最短的节点。算法的关键思想是贪婪地选择当前最短路径,以逐步构建最短路径树。


以下是Python代码示例,演示如何使用Dijkstra算法找到从节点 A 到其他节点的最短路径:

import networkx as nx
import matplotlib.pyplot as plt# 创建一个有向图
G = nx.DiGraph()# 添加节点
nodes = ['A', 'B', 'C', 'D', 'E']
G.add_nodes_from(nodes)# 添加边和权重
edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 5), ('B', 'D', 10), ('C', 'D', 3), ('D', 'E', 7), ('E', 'B', 8)]
G.add_weighted_edges_from(edges)# 定义起点
start_node = 'A'# 运行Dijkstra算法
shortest_paths = nx.single_source_dijkstra(G, source=start_node)# 提取最短路径信息
shortest_distances, shortest_path_predecessors = shortest_paths# 修正labels的格式
labels = {(edge[0], edge[1]): edge[2] for edge in G.edges(data='weight')}# 可视化图
pos = nx.spring_layout(G, seed=42)  # 布局算法,使图看起来更美观plt.figure(figsize=(10, 6))
nx.draw(G, pos, with_labels=True, node_size=800, node_color='lightblue', font_size=12, font_weight='bold')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=10)# 绘制最短路径
for node in nodes:if node != start_node:path = nx.shortest_path(G, source=start_node, target=node)path_edges = [(path[i], path[i + 1]) for i in range(len(path) - 1)]nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2)plt.title("Dijkstra Algorithm - Shortest Paths")
plt.show()# 打印最短路径和距离
for node, distance in shortest_distances.items():if node != start_node:path = nx.shortest_path(G, source=start_node, target=node)print(f"Shortest path from {start_node} to {node}: {path}, Distance: {distance}")

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166878.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac

技巧 | 如何解决 OBS 系统声音无法捕获问题 | Mac 问题描述 由于 macOS 系统限制&#xff0c;桌面音频被禁止&#xff0c;导致在使用 OBS 无法录制桌面音频&#xff0c;只能使用自带麦克风录制。 解决方法 Loopback 介绍 借助 Loopback 的强大功能&#xff0c;可以轻松地…

Arduino驱动BMA220三轴加速度传感器(惯性测量传感器篇)

目录 1、传感器特性 2、硬件原理图 3、驱动程序 BMA220的三轴加速度计是一款具有I2C接口的超小型三轴低g加速度传感器断路器,面向低功耗消费市场应用。它可以测量3个垂直轴的加速度,从而在手机、手持设备、计算机外围设备、人机界面、虚拟现实功能和游戏控制器中感知倾斜、…

CUDA学习笔记(八)Branch Divergence and Unrolling Loop

Avoiding Branch Divergence 有时&#xff0c;控制流依赖于thread索引。同一个warp中&#xff0c;一个条件分支可能导致很差的性能。通过重新组织数据获取模式可以减少或避免warp divergence&#xff08;该问题的解释请查看warp解析篇&#xff09;。 The Parallel Reduction …

Hook原理--逆向开发

今天我们将继续讲解逆向开发工程另一个重要内容--Hook原理讲解。Hook&#xff0c;可以中文译为“挂钩”或者“钩子”&#xff0c;逆向开发中改变程序运行的一种技术。按照如下过程进行讲解 Hook概述Hook技术方式fishhook原理及实例符号表查看函数名称总结 一、Hook概述 在逆…

平板有必要买触控笔吗?推荐的ipad手写笔

iPad之所以能吸引这么多人&#xff0c;主要是因为它的功能出色。用来画画、做笔记&#xff0c;也是一种不错的体验。但如果只是用来看电视和打游戏的话&#xff0c;那就真的有点大材小用了。如果你不需要昂贵的苹果电容笔&#xff0c;也不需要用来专业的绘图&#xff0c;那你可…

在软件测试行业这种情况下,凭什么他能拿25k?我却约面试都难?

在当今竞争激烈的软件测试行业中&#xff0c;近期的招聘市场确实面临一些挑战。大量的求职者争相涌入岗位&#xff0c;许多热衷于功能测试的人士甚至难以找到理想的工作机会。更不幸的是&#xff0c;连自动化测试和性能测试这些专业领域也受到了测试开发人员的竞争压力。然而&a…

【瑞吉外卖部分功能补充】

瑞吉外卖部分功能补充 菜品的启售和停售 在浏览器控制台点击对应功能后可以看到前端发送的请求是&#xff1a;http://localhost:9999/dish/status/1?ids1413342036832100354&#xff0c;请求方式为POST。 接收到前端参数后&#xff0c;进行controller层代码补全&#xff0c…

Spark简介

文章目录 一、简介二、安装1、简介2、本地部署(Local模式)2.1 安装2.2 官方WordCount实例 3、Standlong模式3.1 简介2.2 安装集群2.3 官方测试案例 4、Yarn模式3.1 安装3.2 配置历史服务器3.3 配置查看历史日志 5、Mesos模式6、几种模式对比7、常用端口 三、Yarn模式详解1、简介…

Leetcode—1726.同积元组【中等】

2023每日刷题&#xff08;六&#xff09; Leetcode—1726.同积元组 哈希表解题思路 实现代码 class Solution { public:int tupleSameProduct(vector<int>& nums) {unordered_map<int, int>count;int n nums.size();int i, j;for(i 0; i < n - 1; i) {f…

拓扑几何学

目录 一&#xff0c;欧拉定理 1&#xff0c;平面图论图 2&#xff0c;单连通多面体 3&#xff0c;一般多面体 一&#xff0c;欧拉定理 1&#xff0c;平面图论图 在一个联通无向图中&#xff0c;点数-边数面数 1 如&#xff1a; 7-126 1 如果把最外面的五边形外面也算…

机器学习终极指南:统计和统计建模03/3 — 第 -3 部分

系列上文&#xff1a;机器学习终极指南&#xff1a;特征工程&#xff08;02/2&#xff09; — 第 -2 部分 一、说明 在终极机器学习指南的第三部分中&#xff0c;我们将了解统计建模的基础知识以及如何在 Python 中实现它们&#xff0c;Python 是一种广泛用于数据分析和科学计…

大数据分析实践 | pandas数据质量分析

文章目录 &#x1f4da;数据质量评估的五个维度&#x1f4da;口袋妖怪数据质量分析&#x1f407;导入库和数据&#x1f407;检查数据&#x1f407;缺失值分析&#x1f407;重复值检测&#x1f407;异常值检测 &#x1f4da;数据质量评估的五个维度 Coherent: without semantic …

【刷题篇】反转链表

文章目录 一、206.反转链表二、92.反转链表 ||三、25. K 个一组翻转链表 一、206.反转链表 class Solution { public://使用头插//三个指针也可以ListNode* reverseList(ListNode* head) {if(headnullptr)return nullptr;ListNode* curhead;ListNode* newheadnew ListNode(0);L…

VR智能家居虚拟连接仿真培训系统重塑传统家居行业

家居行业基于对场景的打造及设计&#xff0c;拥有广阔前景&#xff0c;是众多行业里面成为最有可能进行元宇宙落地的应用场景之一。 家居行业十分注重场景的打造及设计&#xff0c;而元宇宙恰恰能通过将人工智能、虚拟现实、大数据、物联网等技术融合提升&#xff0c;带来身临其…

国产开发板上打造开源ThingsBoard工业网关--基于米尔芯驰MYD-JD9X开发板

本篇测评由面包板论坛的优秀测评者“JerryZhen”提供。 本文将介绍基于米尔电子MYD-JD9X开发板打造成开源的Thingsboard网关。 Thingsboard网关是一个开源的软件网关&#xff0c;采用python作为开发语言&#xff0c;可以部署在任何支持 python 运行环境的主机上&#xff0c;灵…

Linux 救援模式

Linux突然坏了 第三次坏了 第一次是找不到盘&#xff0c;修复好了 第二次是找不到卷&#xff0c;但是能启动&#xff0c;启动界面选择救援模式&#xff0c;可以正常使用 第三次&#xff0c;尝试修复卷&#xff0c;启动后&#xff0c;找不到文件系统了&#xff0c;只能从光盘…

使用 Visual Studio Code (VS Code) 作为 Visual C++ 6.0 (VC6) 的编辑器

使用 Visual Studio Code (VS Code) 作为 Visual C 6.0 (VC6) 的编辑器 由于一些众所周知的原因&#xff0c;我们不得不使用经典&#xff08;过时&#xff09;的比我们年龄还大的已有 25 年历史的 VC 6.0 来学习 C 语言。而对于现在来说&#xff0c;这个经典的 IDE 过于简陋&a…

在PS中轻松实现肖像磨皮,感受Imagenomic Portraiture 4的强大

每个人都希望自己的肖像照片看起来漂亮、清晰并且光滑。然而&#xff0c;在处理肖像照片时&#xff0c;要达到这些效果通常需要花费大量时间和精力。如果您正在寻找一种简单快捷的方法来优化您的肖像照片&#xff0c;那么Imagenomic Portraiture 4插件将是您的理想选择。 Imag…

靶机 DC_1

DC_1 信息搜集 存活检测 详细扫描 网页目录扫描 网页信息搜集 cms 为 Drupal 漏洞利用 使用 msf 搜索 drupal 的漏洞 启动 msfconsole搜索 search drupal尝试编号为 0 的漏洞 失败 利用编号为 1 的漏洞 use 1查看需要配置的选项 show options设置目标 ip set rhost 10…

B/S医院手术麻醉临床系统:围术期的认识

手术是治疗很多疾病最有效而且绕不开的措施。而从医生和患者确定了要进行手术治疗的时候&#xff0c;医院相关人员就会开始围着患者团团转&#xff0c;在术前、术中和术后&#xff0c;医生会告诉患者很多事情&#xff0c;患者也会了解很多就诊相关知识。 一、围术期的认识 围术…