Dijkstra算法详细介绍及Python实现方法_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算法不能用于包含负权边的图中，否则可能无法找到正确的最短路径。
内存消耗较大：需要存储所有顶点的距离信息和已访问状态，内存使用随着顶点数增加而增长。
对大规模图不友好：当图变得非常大时，算法将消耗较长的时间计算最短路径。