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

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

Dijkstra算法详细介绍（Python)

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 = ∞
2. 选择最近的未访问顶点B（因为它离A最近，距离为2）。
3. 更新C的距离（因为B到C的距离是1，所以A到C的新距离是A到B的距离加上B到C的距离，即2+1=3）：
   • A = 0, B = 2, C = 3
4. 现在，B和C都是最近未访问过的顶点，我们选择B作为下一个当前顶点（因为它先被检查到）。
5. 更新顶点后，没有更短的路径可以到达C了，我们将B标记为已访问。
6. 现在C是唯一的未访问顶点，我们选择它作为当前顶点。
7. 最终结果是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 < dist[v]:
                dist[v] ← alt;
                prev[v] ← u;
    return dist[];

这段伪代码描述了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 < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_vertex
                heapq.heappush(unvisited_queue, (distance, neighbor))

    return distances, previous_nodes


# Example graph represented as an adjacency list
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 4},
    'C': {'A': 3, 'B': 1, 'D': 5},
    'D': {'B': 4, 'C': 5}
}

start_vertex = 'A'
distances, previous_nodes = dijkstra(graph, start_vertex)

# Function to print the shortest path from start_vertex to end_vertex
def print_shortest_path(previous_nodes, start_vertex, end_vertex):
    path = []
    current_vertex = end_vertex
    while current_vertex is not None and current_vertex != start_vertex:
        path.insert(0, current_vertex)
        current_vertex = previous_nodes[current_vertex]
    if current_vertex is None:
        return "Path does not exist"
    else:
        path.insert(0, start_vertex)
        return path

# Output the results
print("Vertex\tDistance\tPath")
for vertex in graph:
    if vertex != start_vertex:
        dist = distances[vertex]
        path = print_shortest_path(previous_nodes, start_vertex, vertex)
        print(f"{vertex}\t{dist}\t\t{path}")

[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算法的应用场景

1. 路径规划：Dijkstra算法常常被用于道路网络中的最短路径查找，它可以帮助导航系统提供从起点到目的地的最佳路线。
2. 网络路由选择：在互联网中，路由器可以使用Dijkstra算法来选择数据传输的最佳路径。
3. 社交网络分析：分析人与人之间、组织之间的最短联系路径。
4. 运输和物流领域：寻找货物从一个地点到另一个地点成本最低的运输路径。
5. 电路设计：在集成电路布局中，Dijkstra算法可以用于寻找最小延迟路径。
6. 游戏设计：游戏中的NPC（非玩家角色）导航和寻路系统可能使用Dijkstra算法确定行动路径。
7. 电信网络：在电话网络和其他电信网络中定位呼叫的最佳路径。

4.Dijkstra算法优缺点

Dijkstra算法的优点：

1. 准确性：Dijkstra算法总是能找到单源最短路径的精确解，特别是当所有边的权重都是非负数时。
2. 灵活性：在算法的执行过程中如果找到从源点到目标点的最短路径，算法会立即停止处理该目标点，这意味着你可以在任何时候中断算法来查询最短路径。
3. 适用于稠密图：对于边的数量接近于顶点数量平方的稠密图，Dijkstra算法表现良好。
4. 简单性：算法的逻辑相对简单，容易理解和实现。
5. 可以优先处理：通过优先队列的使用，Dijkstra算法可以快速访问当前最短路径的节点。

Dijkstra算法的缺点：

1. 效率问题：使用标准数组存储距离信息时，时间复杂度为

，其中V是顶点的数量。虽然通过使用斐波那契堆等优化措施可以将时间复杂度降低到

，但在最坏的情况下它仍然是效率较低的算法之一。

1. 不适合负权重边：Dijkstra算法不能用于包含负权边的图中，否则可能无法找到正确的最短路径。
2. 内存消耗较大：需要存储所有顶点的距离信息和已访问状态，内存使用随着顶点数增加而增长。
3. 对大规模图不友好：当图变得非常大时，算法将消耗较长的时间计算最短路径。