【启发式算法】Dijkstra算法详细介绍（Python）

06-01 1684阅读

📢本篇文章是博主博主人工智能学习以及算法研究时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏：

【】人工智能】- 【启发式算法】（7）---《Dijkstra算法详细介绍（Python）》

Dijkstra算法详细介绍（Python

1. Dijkstra算法介绍

2.文献阅读

问题1：构造n个节点间总长度最小的树（最小生成树）

问题2：寻找给定两点P和Q间总长度最小的路径

总结

2.Dijkstra算法原理

核心思想：

示例：

推理公式：

[Python] Dijkstra算法实现

[Results] 运行结果

3. Dijkstra算法的应用场景

4.Dijkstra算法优缺点

Dijkstra算法的优点：

Dijkstra算法的缺点：

1. Dijkstra算法介绍

Dijkstra算法，全称迪杰斯特拉算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出的，是一种用于解决图中的最短路径问题的算法。这种算法适用于带权重的图，其中每条边有一个非负的权重值。

这篇论文发表于1959年的《Numerische Mathematik》期刊第1期，第269-271页，《A Note on Two Problems in Connexion with Graphs》。在这篇论文中，他不仅描述了这个算法，还提供了第一次正式的最短路径问题算法理论证明。这篇论文的题目虽然翻译成中文是《关于与图相关的两个问题的说明》，但它在算法史上有着非常重要的地位，因为其中描述的Dijkstra算法成为了解决图中最短路径问题的基石。

2.文献阅读

《A Note on Two Problems in Connexion with Graphs》的核心内容主要针对两个问题：

问题1：构造n个节点间总长度最小的树（最小生成树）

基本思路：将边分为3个集合（确定属于生成树的边的集合I、待选边集合II、剩余边集合III），将节点分为2个集合（已连接集合A、剩余节点集合B）。初始时，任选一节点作为集合A的唯一成员，所有以此节点为终点的边放入集合II，集合I为空。
构造步骤：
- 步骤1：从集合II中选出最短的边，将其移出集合II并加入集合I，同时将对应的节点从集合B转移到集合A。
- 步骤2：考虑刚转移到集合A的节点与集合B中节点相连的边，若边长比集合II中对应边长则被舍弃，若更短则替换集合II中的对应边并舍弃后者。然后返回步骤1重复此过程，直到集合II和III均为空，此时集合I中的边即构成所需的最小生成树。
- 优势：相较于J.B. KRUSKAL、H. LOBERMAN和A. WEINBERGER的方法，该方法无需预先所有对边按长度排序，且只需同时存储最多n条边的数据（集合I和II中的边以及步骤2中考虑的边），而其他方法即使边的长度是节点坐标的可计算函数，也需要同时存储所有边的数据。
  
  问题2：寻找给定两点P和Q间总长度最小的路径
  - 基本思路：利用若R是P到Q的最小路径上的节点，则知道P到Q的最小路径也就知道P到R的最小路径这一事实。在解决方案中，按路径长度递增的顺序构造P到其他节点的最小路径，直到到达Q。
  - 具体步骤：
    - 初始状态：所有节点在集合C，所有边在集合III。将节点P转移到集合A，然后反复执行以下步骤。
    - 步骤1：考虑连接刚转移到集合A的节点与集合B或C中的节点R的所有边r。若R属于集合B，判断使用边r是否能获得比已知路径更短的P到R的路径，若不能则边r被舍弃，若能则替换集合II中的对应边并舍弃后者；若R属于集合C，则将R加入集合B并将边r加入集合II。
    - 步骤2：集合B中的每个节点通过集合I中的一条边和集合II中的一条边与节点P相连，每个节点B都有一个到P的距离。将集合B中到P距离最小的节点转移到集合A，对应的边从集合II转移到集合I。然后返回步骤1重复此过程，直到节点Q被转移到集合A，此时即找到解决方案。
    - 优势：与L. R. FORD的方法相比，无论边的数量如何，该方法无需同时存储所有边的数据，只需存储集合I和II中的边，且这个数量总是小于n，同时所需的工作量也明显更少。
      
      总结
      
      该论文主要介绍了两种解决图论问题的方法，分别针对构造最小生成树和寻找两点间最短路径。这两种方法在数据存储和计算工作量方面相较于其他方法具有优势，能够更高效地解决相应的问题。
      
      《A Note on Two Problems in Connexion with Graphs》中没有直接提及“Dijkstra算法”这个名称。但其中提出的解决最短路径问题的方法后来被广泛称为Dijkstra算法。文件中针对最短路径问题所描述的解决方法，其核心思路与Dijkstra算法完全一致，即通过维护节点集合和边集合的特定方式，逐步确定从起点到其他节点的最短路径。
      
      2.Dijkstra算法原理
      
      想象一下，你在一座迷宫里，你想要从起点A到达终点B并找到最短的路径，那么你可以使用Dijkstra算法。这个算法会帮助你计算出从起点到所有其他点的最短距离，并且最终告诉你到达终点B的最短路径是什么。
      
      核心思想：
      1. 初始化：从一个顶点开始（我们称之为源点），将源点到自身的距离设为0，而到其他顶点的距离设为无穷大。
      2. 选择最近顶点：在所有未被访问过的顶点中，选择距离源点最近的一个顶点（称之为当前顶点）。
      3. 更新距离：检查通过当前顶点可以到达的所有其他未被访问过的顶点，如果通过当前顶点到达这些顶点的距离比之前已知的更短，就更新这些顶点的距离。
      4. 标记已访问：将当前顶点标记为已访问，并从待访问顶点集合中移除。
      5. 重复以上步骤：重复步骤2到4，直到所有的顶点都被访问过或者目标顶点被访问。
      示例：
      
      假设我们有如下的图中的四个节点和它们之间的边及其权重：
```
  A---(2)---B
  |         |
(3)        (1)
  |         |
  ----------------C
```
      我们要计算从A到C的最短路径。
      1. 初始化：
        
        A = 0, B = ∞, C = ∞
        
        选择最近的未访问顶点B（因为它离A最近，距离为2）。
        
        更新C的距离（因为B到C的距离是1，所以A到C的新距离是A到B的距离加上B到C的距离，即2+1=3）：
        
        A = 0, B = 2, C = 3
        
        现在，B和C都是最近未访问过的顶点，我们选择B作为下一个当前顶点（因为它先被检查到）。
        
        更新顶点后，没有更短的路径可以到达C了，我们将B标记为已访问。
        
        现在C是唯一的未访问顶点，我们选择它作为当前顶点。
        
        最终结果是A到C的最短路径是3。
      推理公式：
      
      Dijkstra算法没有一个单一的公式，但是可以用伪代码来说明它的逻辑：
```
function Dijkstra(Graph, source):
    dist[source] ← 0; // 初始化距离表
    for each vertex v in Graph: 
        if v ≠ source
            dist[v] ← ∞; 
            prev[v] ← undefined; // 前驱节点，用于记录最短路径
            Q ← all vertices in Graph; // 所有顶点的集合
    while Q is not empty:
        u ← vertex in Q with min dist[u];
        remove u from Q;
        for each neighbor v of u: // 遍历u的所有邻居v
            alt ← dist[u] + length(u, v);
            if alt  
        这段伪代码描述了Dijkstra算法的基本流程，其中dist[]存储从源点到各个点的距离，prev[]用来存储最短路径树，以便最后能回溯出最短路径。 
[Python] Dijkstra算法实现 
        下面给出一个简单的Python实现Dijkstra算法的程序，以及一个示例图和运行结果。这个程序会计算从源点到图中所有其他节点的最短路径，并输出最短距离和路径。 
"""《Dijkstra算法程序》
    时间：2025.03.06
    作者：不去幼儿园
"""
import heapq
def dijkstra(graph, start):
    -distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    -previous_nodes = {vertex: None for vertex in graph}
    -unvisited_queue = [(0, start)]
    while unvisited_queue:
        current_distance, current_vertex = heapq.heappop(unvisited_queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance  
[Results] 运行结果 
 
        上述代码中的例子图，它展示了10个节点之间的连接关系和权重。图形由顶点（A到J）和它们之间的边与权重组成：  
    A
   /|\
  B C D
 / | \
E  F  |
 \ | /
  G H
   \ /
    I
    |
    J
 
每个节点与其直接相连的节点都有特定的权重。下面是这些连接关系和对应的权重： 
```
      - A 到 B: 2
      - A 到 C: 3
      - A 到 D: 1
      - B 到 C: 1
      - B 到 D: 4
      - B 到 E: 5
      - C 到 D: 1
      - C 到 E: 6
      - D 到 E: 2
      - E 到 F: 7
      - E 到 G: 9
      - F 到 G: 8
      - F 到 H: 5
      - G 到 H: 3
      - G 到 I: 6
      - H 到 I: 7
      - I 到 J: 2
        Vertex Distance Path B 2 ->A->B C 3 ->A->C D 1 ->A->D E 3 ->A->D->E F 6 ->A->D->E->F G 10 ->A->D->E->G H 8 ->A->D->E->F->H I 11 ->A->D->E->F->H->I J 13 ->A->D->E->F->H->I->J
        
        3. Dijkstra算法的应用场景
        
        路径规划：Dijkstra算法常常被用于道路网络中的最短路径查找，它可以帮助导航系统提供从起点到目的地的最佳路线。
        
        网络路由选择：在互联网中，路由器可以使用Dijkstra算法来选择数据传输的最佳路径。
        
        社交网络分析：分析人与人之间、组织之间的最短联系路径。
        
        运输和物流领域：寻找货物从一个地点到另一个地点成本最低的运输路径。
        
        电路设计：在集成电路布局中，Dijkstra算法可以用于寻找最小延迟路径。
        
        游戏设计：游戏中的NPC（非玩家角色）导航和寻路系统可能使用Dijkstra算法确定行动路径。
        
        电信网络：在电话网络和其他电信网络中定位呼叫的最佳路径。
        
        4.Dijkstra算法优缺点
        
        Dijkstra算法的优点：
        
        准确性：Dijkstra算法总是能找到单源最短路径的精确解，特别是当所有边的权重都是非负数时。
        
        灵活性：在算法的执行过程中如果找到从源点到目标点的最短路径，算法会立即停止处理该目标点，这意味着你可以在任何时候中断算法来查询最短路径。
        
        适用于稠密图：对于边的数量接近于顶点数量平方的稠密图，Dijkstra算法表现良好。
        
        简单性：算法的逻辑相对简单，容易理解和实现。
        
        可以优先处理：通过优先队列的使用，Dijkstra算法可以快速访问当前最短路径的节点。
        
        Dijkstra算法的缺点：
        
        效率问题：使用标准数组存储距离信息时，时间复杂度为 $O(V^2)$ ，其中V是顶点的数量。虽然通过使用斐波那契堆等优化措施可以将时间复杂度降低到 $O((E+V)logV)$ ，但在最坏的情况下它仍然是效率较低的算法之一。
        
        不适合负权重边：Dijkstra算法不能用于包含负权边的图中，否则可能无法找到正确的最短路径。
        
        内存消耗较大：需要存储所有顶点的距离信息和已访问状态，内存使用随着顶点数增加而增长。
        
        对大规模图不友好：当图变得非常大时，算法将消耗较长的时间计算最短路径。
        
        更多启发式算法文章，请前往：【启发式算法】专栏
        
        博客都是给自己看的笔记，如有误导深表抱歉。文章若有不当和不正确之处，还望理解与指出。由于部分文字、图片等来源于互联网，无法核实真实出处，如涉及相关争议，请联系博主删除。如有错误、疑问和侵权，欢迎评论留言联系作者，或者添加VX：Rainbook_2，联系作者。✨

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

高速稳定云服务器9.9元起