迪杰斯特拉 (Dijkstra)算法

想象一下,你住在一个很大的城市,这个城市有很多地方(我们称之为“顶点”),这些地方之间有许多道路(我们称之为“边”)。你想从家里出发,找到去城市中其他地方的最快路线。这个问题就像Dijkstra算法要解决的问题。

### Dijkstra算法的故事

#### 设想一个城市:

在这个城市中,每条道路都有一个标牌,上面写着走这条路需要的时间。这些标牌上的数字就是我们所谓的“权值”。有些路可能比较远,所以时间就长(权值大);而有些路很近,时间就短(权值小)。重要的是,这些标牌上的时间都是正数,也就是说,走这条路总是需要花费时间的,不会有负数的时间。

#### 目标:

你想知道,从家里出发,去每一个地方的最快路线是什么。

#### Dijkstra算法怎么做:

1. **出发点**:首先,把你的家(起点)放在一个特殊的列表里,并标记为“已经到达”。这个列表会帮助你跟踪你已经知道最短路线的地方。

2. **初始状态**:一开始,你只知道从家到家的时间是0(因为不需要移动)。对于其他所有地方,你暂时标记为“需要很长时间才能到达”。

3. **寻找最短路径**:
   - 看看从家出发有哪些直接相连的地方(通过道路连接的地方)。
   - 选择一个你现在知道的最短路线的地方(比如,你知道从家到公园只需要10分钟),然后从这个地方出发,看看能到达哪些新的地方。
   - 计算如果通过这个新的地方,到达其他地方是否比之前想到的路线更快。如果是,那就更新这些地方所需的时间。

4. **重复**:
   - 把这个新到达的地方也标记为“已经到达”。
   - 重复这个过程:每次选择一个当前最短的地方进行扩展,更新到达其他地方的时间,直到所有地方都被标记为“已经到达”。

5. **完成**:
   - 当所有地方都被标记为“已经到达”时,你就知道了从家到每个地方的最快路线。

### Dijkstra算法的重点

- **贪心策略**:每次总是选择当前看来最快的路线去探索新的地方。这就像在走迷宫时,每次都选择离出口最近的通道。

- **非负权值**:因为所有的道路(边)的时间都是正数,所以每次你确定了一条路线,它一定是最短的。这是Dijkstra算法能够正常工作的关键。

### 小结

Dijkstra算法就像是一个聪明的导航系统,它帮助你从一个出发点快速找到去其他所有地方的最佳路线。记住,每次你都选择当前最短的路径,这样就能保证最终找到的是最短的路线。

当然,接下来我们可以进一步通过一些例子和比喻来帮助理解Dijkstra算法。

### 举个例子

假设你现在住在A点,你想去B、C、D、E这些地方。我们用简单的数字来表示从一个地方到另一个地方的时间(或者说距离):

- A到B需要4分钟
- A到C需要2分钟
- B到C需要1分钟
- B到D需要5分钟
- C到D需要8分钟
- C到E需要10分钟
- D到E需要2分钟

#### 步骤解析

1. **初始状态**:  
   - 你在A点,所以A到A的时间是0。
   - 其他地方B、C、D、E的初始时间都是“无限大”,因为你还不知道怎么去。

2. **第一次选择**:  
   - 从A出发,你可以直接到B或C。
   - 选择C,因为A到C只需要2分钟,比到B的4分钟更短。

3. **更新路径**:  
   - 已经知道从A到C是2分钟。
   - 看看从C可以去哪些地方:可以去D(8分钟)和E(10分钟)。
   - 计算从A到D经过C需要10分钟(A到C 2分钟 + C到D 8分钟)。
   - 计算从A到E经过C需要12分钟(A到C 2分钟 + C到E 10分钟)。

4. **第二次选择**:  
   - 现在已知的时间有:A到B 4分钟,A到D 10分钟,A到E 12分钟。
   - 选择B,因为A到B只需要4分钟。

5. **再次更新路径**:  
   - 确定从A到B需要4分钟。
   - 看看B可以到哪里:可以到C(1分钟)和D(5分钟)。
   - 通过B到C是3分钟(A到B 4分钟 + B到C 1分钟),但这比直接到C的2分钟更长,所以不更新。
   - 计算从A到D经过B需要9分钟(A到B 4分钟 + B到D 5分钟),比之前的10分钟更短,所以更新A到D为9分钟。

6. **第三次选择**:  
   - 现在已知的时间有:A到C 2分钟,A到D 9分钟,A到E 12分钟。
   - 选择D,因为A到D需要9分钟。

7. **最后更新**:
   - 确定从A到D需要9分钟。
   - 通过D可以到E,计算从A到E经过D需要11分钟(A到D 9分钟 + D到E 2分钟),比之前的12分钟更短,所以更新A到E为11分钟。

8. **完成**:
   - 现在你知道了从A到B是4分钟,从A到C是2分钟,从A到D是9分钟,从A到E是11分钟。

### 结论

通过这种方式,Dijkstra算法帮助你找到了从起点到所有其他地方的最短路径。这种方法不仅适用于城市交通规划,还可以用于网络路由、游戏路径寻路等许多实际问题。

接下来我们可以进一步通过一些例子和比喻来帮助理解Dijkstra算法。

### 举个例子

假设你现在住在A点,你想去B、C、D、E这些地方。我们用简单的数字来表示从一个地方到另一个地方的时间(或者说距离):

- A到B需要4分钟
- A到C需要2分钟
- B到C需要1分钟
- B到D需要5分钟
- C到D需要8分钟
- C到E需要10分钟
- D到E需要2分钟

#### 步骤解析

1. **初始状态**:  
   - 你在A点,所以A到A的时间是0。
   - 其他地方B、C、D、E的初始时间都是“无限大”,因为你还不知道怎么去。

2. **第一次选择**:  
   - 从A出发,你可以直接到B或C。
   - 选择C,因为A到C只需要2分钟,比到B的4分钟更短。

3. **更新路径**:  
   - 已经知道从A到C是2分钟。
   - 看看从C可以去哪些地方:可以去D(8分钟)和E(10分钟)。
   - 计算从A到D经过C需要10分钟(A到C 2分钟 + C到D 8分钟)。
   - 计算从A到E经过C需要12分钟(A到C 2分钟 + C到E 10分钟)。

4. **第二次选择**:  
   - 现在已知的时间有:A到B 4分钟,A到D 10分钟,A到E 12分钟。
   - 选择B,因为A到B只需要4分钟。

5. **再次更新路径**:  
   - 确定从A到B需要4分钟。
   - 看看B可以到哪里:可以到C(1分钟)和D(5分钟)。
   - 通过B到C是3分钟(A到B 4分钟 + B到C 1分钟),但这比直接到C的2分钟更长,所以不更新。
   - 计算从A到D经过B需要9分钟(A到B 4分钟 + B到D 5分钟),比之前的10分钟更短,所以更新A到D为9分钟。

6. **第三次选择**:  
   - 现在已知的时间有:A到C 2分钟,A到D 9分钟,A到E 12分钟。
   - 选择D,因为A到D需要9分钟。

7. **最后更新**:
   - 确定从A到D需要9分钟。
   - 通过D可以到E,计算从A到E经过D需要11分钟(A到D 9分钟 + D到E 2分钟),比之前的12分钟更短,所以更新A到E为11分钟。

8. **完成**:
   - 现在你知道了从A到B是4分钟,从A到C是2分钟,从A到D是9分钟,从A到E是11分钟。

### 结论

通过这种方式,Dijkstra算法帮助你找到了从起点到所有其他地方的最短路径。这种方法不仅适用于城市交通规划,还可以用于网络路由、游戏路径寻路等许多实际问题。

Dijkstra算法确实是一种**贪心算法**。贪心算法的核心思想是每一步都做出在当前看来是最优的选择,希望通过局部最优解最终达到全局最优解。

在Dijkstra算法中,这种贪心策略体现在每一步总是选择当前已知的最短路径去扩展。具体来说:

1. **选择当前最近的顶点**:在每一步中,算法会选择从起点到当前未处理顶点中距离最短的那个顶点。这是基于贪心原则的,因为它选择了看起来最有希望通向最终最短路径的那条路。

2. **逐步扩展路径**:一旦选择了一个顶点,算法会检查通过这个顶点能否找到更短的路径到达其他未处理的顶点。如果可以,则更新这些顶点的最短路径信息。

通过这样的逐步扩展和更新路径,Dijkstra算法能够高效地找到从起点到所有其他顶点的最短路径。正因为它每一步都做出局部最优的选择,这才符合贪心算法的特征。

### 什么是贪心算法?

想象一下,你在一个糖果店里,有一大堆不同口味的糖果。你的任务是用尽可能少的钱买到一定数量的糖果,这样你就可以既省钱又能吃到很多糖果。贪心算法就像是你在挑选糖果时的一种聪明策略。

### 贪心算法的基本思想

贪心算法的基本思想是:每一步都选择当前看起来最好的选择,而不去考虑未来的选择。就像在糖果店里,你每次都挑选那些最便宜的糖果,因为这样看起来你用更少的钱可以买到更多的糖果。

### 举个例子:糖果店的故事

假设你有10元钱,你想买尽可能多的糖果。糖果店里有三种糖果:

1. 巧克力糖果:每颗3元
2. 水果糖果:每颗2元
3. 奶油糖果:每颗1元

你想用这10元钱买最多的糖果。贪心算法会建议你每次都选择那些最便宜的糖果,因为这样你可以用更少的钱买到更多的糖果。

- **步骤1**:你有10元,先买奶油糖果,因为它最便宜,只要1元。买1颗,剩下9元。
- **步骤2**:再买一颗奶油糖果,又花了1元,还剩8元。
- **步骤3**:继续买奶油糖果,直到你花完10元。

这样,你一共可以买到10颗奶油糖果。

### 为什么叫“贪心”?

因为贪心算法总是选择当前看起来最好的东西,就像一个小朋友看到糖果山,总是想先拿最多的糖果,而不是先考虑不同糖果的组合。它不去想以后可能会有什么更好的选择,只管眼前的利益。

### 贪心算法的优点和缺点

**优点**:
- **简单快捷**:贪心算法通常很简单,计算速度快。
- **容易实现**:因为每一步都只关注眼前的选择,所以实现起来比较简单。

**缺点**:
- **不总是最优**:贪心算法有时候可能不会找到问题的最佳解决方案。就像在糖果店的例子中,如果你特别喜欢巧克力糖果,贪心算法可能不会满足你的口味偏好。

### 什么时候适合用贪心算法?

贪心算法适用于那些可以通过一系列局部最优解来得到全局最优解的问题。比如:

- **找零问题**:如果你有不同面值的硬币,想用最少的硬币凑出某个金额,贪心算法可以选每次选择面值最大的硬币。
- **最小生成树问题**:在网络连接问题中,贪心算法可以帮助找到连接所有点的最短路径。

### 小结

贪心算法就像是一个聪明的策略,帮助你在做选择时,每次都选择看起来最好的那个。当你面对一个问题,不知道怎么开始时,可以想想贪心算法,因为它可能是一个快速又简单的方法。

让我带你进入一个程序员的世界,讲述一个关于Dijkstra算法的故事。

---

在一座繁华的城市里,有一个叫小明的程序员,他是一位典型的ESFP类型:热情、活泼,喜欢探索新事物,尤其对解决实际问题充满兴趣。小明在一家科技公司工作,公司正在开发一款导航应用,需要用到算法来计算最短路径。

### 小明的任务

一天,老板找到小明:“我们需要在新的导航应用中实现一个功能,计算用户从一个地点到另一个地点的最短路径。你能负责这部分吗?”

小明心想,这正是一个展示他技术能力的好机会。他立刻想到Dijkstra算法,这是一个经典的图算法,可以用于计算加权图中单源节点到其他节点的最短路径,特别适合解决导航问题。

### 理解Dijkstra算法

小明首先回顾了一下Dijkstra算法的基本原理:

1. **初始化**:从起点开始,把起点到自己的距离设为0,其他所有节点的距离设为无穷大。
2. **选择当前距离最短的节点**:在未处理的节点中,选择距离起点最近的节点。
3. **更新邻居的距离**:对于当前节点的每一个邻居节点,计算从起点经过当前节点到达邻居的距离。如果这个距离比目前记录的距离短,就更新这个距离。
4. **重复步骤2和3**:直到所有节点都被处理过。

为了实现这个算法,小明决定用Python来编写代码。

### 编写代码

小明打开他的电脑,开始写代码。他知道要用一个优先队列来高效选择当前距离最短的节点,于是他使用了Python的`heapq`库。

```python
import heapq

def 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] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances
```

### 解释代码

- **初始化距离**:他用一个字典`distances`来记录从起点到每个节点的最短距离。
- **优先队列**:使用`heapq`来管理待处理节点,以保证总是选择当前距离最短的节点。
- **更新逻辑**:对于每个节点,检查其邻居节点,计算经过当前节点到达邻居的距离。如果这个新距离更短,就更新记录。

### 调试与应用

小明用一个简单的图来测试他的代码:

```python
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))
```

他期待的输出是:
```
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
```

这个结果表示从A出发,到B最短路径为1,到C为3,到D为4,这正是他所期望的。

### 反思与总结

小明成功地实现了Dijkstra算法并应用在了公司的导航应用中。他意识到,Dijkstra算法不仅仅是一个技术工具,更是一种解决问题的思维方式。每一步都在寻找当前最优解,逐步逼近最终目标。

通过这次项目,小明更加确信,算法就像生活中的选择:每一步都要尽可能做出最优选择,最终才能走到理想的终点。

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

禁用达梦DEM的agent

agent占用内存较多&#xff0c;实际没什么使用&#xff0c;考虑停止agent 应该切换到root执行停止 cd /dm/dmdbms/tool/dmagent/service/ ./DmAgentService stop禁用

多维高斯分布的信息熵和KL散度计算

多维高斯分布是一种特殊的多维随机分布&#xff0c;应用非常广泛&#xff0c;很多现实问题的原始特征分布都可以看作多维高斯分布。本文以数据特征服从多维高斯分布的多分类任务这一理想场景为例&#xff0c;从理论层面分析数据特征和分类问题难度的关系注意&#xff0c;本文分…

【ESP32CAM+Android+C#上位机】ESP32-CAM在STA或AP模式下基于UDP与手机APP或C#上位机进行视频流/图像传输

前言: 本项目实现ESP32-CAM在STA或AP模式下基于UDP与手机APP或C#上位机进行视频流/图像传输。本项目包含有ESP32源码(arduino)、Android手机APP源码以及C#上位机源码,本文对其工程项目的配置使用进行讲解。实战开发,亲测无误。 AP模式,就是ESP32发出一个WIFI/热点提供给电…

Banana Pi BPI-CanMV-K230D-Zero 采用嘉楠科技 K230D RISC-V芯片设计

概述 Banana Pi BPI-CanMV-K230D-Zero 采用嘉楠科技 K230D RISC-V芯片设计,探索 RISC-V Vector1.0 的前沿技术&#xff0c;选择嘉楠科技的 Canmv K230D Zero 开发板。这款创新的开发板是由嘉楠科技与香蕉派开源社区联合设计研发&#xff0c;搭载了先进的勘智 K230D 芯片。 K230…

RocketMQ: Producer与Consumer 最佳实践

Producer 1 &#xff09;发送消息注意事项 1.1 一个应用尽可能用一个 Topic&#xff0c;消息子类型用 tags 来标识&#xff0c;tags 可以由应用自由设置。只有发送消息设置了tags&#xff0c;消费方在订阅消息时&#xff0c;才可以利用 tags 在 broker 做消息过滤 message.setT…

MCGSMCGS昆仑通态触摸屏

MCGS昆仑通态触摸屏应用实例详解 1目录设置 本案例讲了两个窗口的互相调用 创建工程 首先创建一个新工程 打开软件 McgsPro组态软件 菜单栏&#xff1a;文件&#xff1a;新建工程 打开工程设置窗口 HMI配置中应该是对应的不同型号的触摸屏&#xff0c; 选择一个类型&#x…

低温存储开关机问题

问题&#xff1a; 某消费电子产品在进行可靠性实验室&#xff0c;在低温-30C存储两个小时后&#xff0c;上电不开机。在常温25C时&#xff0c;开关机正常。 分析&#xff1a; 1、接串口抓log信息&#xff0c;从打印信息可以看出uboot可以起来&#xff0c;在跑kernel时&#x…

【JavaEE进阶】 JavaScript

本节⽬标 了解什么是JavaScript, 学习JavaScript的常⻅操作, 以及使⽤JQuery完成简单的⻚⾯元素操作. 一. 初识 JavaScript 1.JavaScript 是什么 JavaScript (简称 JS), 是⼀个脚本语⾔, 解释型或即时编译型的编程语⾔. 虽然它是作为开发Web⻚⾯的脚本语⾔⽽出名&#xff0c;…

蓝桥杯每日真题 - 第23天

题目&#xff1a;&#xff08;直线&#xff09; 题目描述&#xff08;12届 C&C B组C题&#xff09; 解题思路&#xff1a; 题目理解: 在平面直角坐标系中&#xff0c;从给定的点集中确定唯一的直线。 两点确定一条直线&#xff0c;判断两条直线是否相同&#xff0c;可通过…

战略思维:破解复杂世界的系统性智慧

在当今快速演变且错综复杂的时代背景下&#xff0c;战略思维已然成为个人、组织乃至国家在应对挑战和实现目标过程中的核心能力。它不仅是一种思考模式&#xff0c;更是一套系统且富有智慧的工具&#xff0c;助力我们在混沌的环境中精准定位方向、敏锐捕捉机遇。 一、目…

html+js实现图片的放大缩小等比缩放翻转,自动播放切换,顺逆时针旋转

效果图&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>图片预览</title><sty…

postgresql|数据库开发|python的psycopg2库按指定顺序批量执行SQL文件(可离线化部署)

一、 psycopg2简介 psycopg2库是python的一个可直接操作postgresql数据库的类库&#xff0c;是一个用于Python编程语言的PostgreSQL数据库适配器。它允许开发人员使用Python语言与PostgreSQL数据库进行交互和操作&#xff0c;不同于java&#xff0c;需要专用的一个驱动&#…

基于Java Springboot个人健康管理网站

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…

论文概览 |《Journal of Urban Technology》2024 Vol.31 Issue.2

本次给大家整理的是《Journal of Urban Technology》杂志2024年第31卷第2期的论文的题目和摘要&#xff0c;一共包括6篇SCI论文&#xff01; 论文1 Aerial Video Surveillance in a Megacity: A Case Study in Santiago, Chile 大城市中的空中视频监控&#xff1a;智利圣地亚哥…

模型 I/O 与 LangChain 实践

模型 I/O 与 LangChain 实践 本文是《LangChain 实战课》第 4 节——模型 I/O&#xff1a;输入提示、调用模型、解析输出的一些学习笔记与总结。这篇文章将围绕模型 I/O 的基本概念、LangChain 提供的最佳实践以及如何通过 LangChain 实现高效的结构化数据处理展开。 什么是模…

【编译原理】词法、语法、语义实验流程内容梳理

编译原理实验有点难&#xff0c;但是加上ai的辅助就会很简单&#xff0c;下面梳理一下代码流程。 全代码在github仓库中&#xff0c;链接&#xff1a;NeiFeiTiii/CompilerOriginTest at Version2.0&#xff0c;感谢star一下 一、项目结构 关键内容就是里面的那几个.c和.h文件。…

uni-app 认识条件编译,了解多端部署

一. 前言 在使用 uni-app 进行跨平台开发的过程中&#xff0c;经常会遇到需要针对不同平台或不同环境进行条件编译的情况。条件编译是一种在编译过程中根据指定条件选择不同代码路径的技术&#xff0c;可以帮助我们在不同平台或环境下编写不同的代码&#xff0c;以适应不同的平…

使用ChatGPT生成和优化电子商务用户需求规格说明书

在电子商务项目开发中&#xff0c;用户需求规格说明书&#xff08;User Requirement Specification, URS&#xff09;是团队沟通与项目成功的基石。然而&#xff0c;面对复杂多变的需求&#xff0c;如何快速生成清晰、完整且具备说服力的文档&#xff1f;这正是AI工具的用武之地…

微信小程序包之加农炮游戏

微信小程序 - 气球射击游戏 项目简介 这是一个简单有趣的微信小程序射击游戏。玩家通过控制屏幕底部的加农炮&#xff0c;射击从上方降落的蓝色气球。游戏考验玩家的反应能力和瞄准技巧。 游戏规则 点击屏幕任意位置发射炮弹大炮会自动对准点击位置击中气球获得10分如果气球触…

JavaWeb——案例——tlias教学辅助系统

7.1.1. Restful 7.1.2. 统一响应结果 7.1.3. 开发流程 7.2. 部门管理 7.2.1. 查询部门-思路 7.2.2. 日志技巧 Slf4j可以替换private static Logger log LoggerFactory.getLogger(DeptController.class); 7.2.3. 删除部门-思路 7.2.4. 新增部门-思路 7.2.5. Controller优化 …