📢本篇文章是博主博主人工智能学习以及算法研究时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏：
【】人工智能】- 【启发式算法】（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的最短路径是什么。
核心思想：
- 初始化：从一个顶点开始（我们称之为源点），将源点到自身的距离设为0，而到其他顶点的距离设为无穷大。
- 选择最近顶点：在所有未被访问过的顶点中，选择距离源点最近的一个顶点（称之为当前顶点）。
- 更新距离：检查通过当前顶点可以到达的所有其他未被访问过的顶点，如果通过当前顶点到达这些顶点的距离比之前已知的更短，就更新这些顶点的距离。
- 标记已访问：将当前顶点标记为已访问，并从待访问顶点集合中移除。
- 重复以上步骤：重复步骤2到4，直到所有的顶点都被访问过或者目标顶点被访问。
示例：
假设我们有如下的图中的四个节点和它们之间的边及其权重：
A---(2)---B
| |
(3) (1)
| |
----------------C
我们要计算从A到C的最短路径。
初始化：
- 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 < 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算法的应用场景
路径规划：Dijkstra算法常常被用于道路网络中的最短路径查找，它可以帮助导航系统提供从起点到目的地的最佳路线。
网络路由选择：在互联网中，路由器可以使用Dijkstra算法来选择数据传输的最佳路径。
社交网络分析：分析人与人之间、组织之间的最短联系路径。
运输和物流领域：寻找货物从一个地点到另一个地点成本最低的运输路径。
电路设计：在集成电路布局中，Dijkstra算法可以用于寻找最小延迟路径。
游戏设计：游戏中的NPC（非玩家角色）导航和寻路系统可能使用Dijkstra算法确定行动路径。
电信网络：在电话网络和其他电信网络中定位呼叫的最佳路径。
4.Dijkstra算法优缺点
Dijkstra算法的优点：
准确性：Dijkstra算法总是能找到单源最短路径的精确解，特别是当所有边的权重都是非负数时。
灵活性：在算法的执行过程中如果找到从源点到目标点的最短路径，算法会立即停止处理该目标点，这意味着你可以在任何时候中断算法来查询最短路径。
适用于稠密图：对于边的数量接近于顶点数量平方的稠密图，Dijkstra算法表现良好。
简单性：算法的逻辑相对简单，容易理解和实现。
可以优先处理：通过优先队列的使用，Dijkstra算法可以快速访问当前最短路径的节点。
Dijkstra算法的缺点：
效率问题：使用标准数组存储距离信息时，时间复杂度为
，其中V是顶点的数量。虽然通过使用斐波那契堆等优化措施可以将时间复杂度降低到
，但在最坏的情况下它仍然是效率较低的算法之一。
不适合负权重边：Dijkstra算法不能用于包含负权边的图中，否则可能无法找到正确的最短路径。
内存消耗较大：需要存储所有顶点的距离信息和已访问状态，内存使用随着顶点数增加而增长。
对大规模图不友好：当图变得非常大时，算法将消耗较长的时间计算最短路径。
更多启发式算法文章，请前往：【启发式算法】专栏
博客都是给自己看的笔记，如有误导深表抱歉。文章若有不当和不正确之处，还望理解与指出。由于部分文字、图片等来源于互联网，无法核实真实出处，如涉及相关争议，请联系博主删除。如有错误、疑问和侵权，欢迎评论留言联系作者，或者添加VX：Rainbook_2，联系作者。✨