狄克斯特拉算法

#狄克斯特拉算法

• 什么是狄克斯特拉算法
• 操作步骤
• Python 实现
• 负权边问题

#什么是狄克斯特拉算法

狄克斯特拉（Dijkstra）算法用于在加权图中求最短路径。广度优先搜索找的是段数最少的路径（非加权图），狄克斯特拉算法找的是总权重最小的路径（加权图）。

核心思想：每次从未处理的节点中选出开销最小的，更新其邻居的开销。

#操作步骤

以 A 为起点、G 为终点为例：

B --3-- E
|       |
2       4
|       |
A --6-- D --9-- G
|       |
5       7
|       |
C --8-- F

第 1 步：初始化开销表

A=0  B=∞  C=∞  D=∞  E=∞  F=∞  G=∞

第 2 步：从 A 出发，更新邻居的开销

B = 0 + 2 = 2
C = 0 + 5 = 5

开销表: A=0  B=2  C=5  D=∞  E=∞  F=∞  G=∞

第 3 步：选出开销最小且未处理的节点 B（2），确定 A→B 为最短路径，处理 B

B 的邻居: D 和 E
D = 2 + 1 = 3 < ∞ → 更新
E = 2 + 3 = 5 < ∞ → 更新
B→C: 2 + 6 = 8 > 5 → 不更新

开销表: A=0  B=2  C=5  D=3  E=5  F=∞  G=∞

第 4 步：选开销最小的未处理节点 D（3），确定 A→B→D 为最短路径

开销表: A=0  B=2  C=5  D=3  E=5  F=∞  G=∞

继续：选 C（5），F = 5+8=13 → 更新；选 E（5），G = 5+9=14 → 更新；选 F（13），F→G = 13+7=20 > 14 → 不更新；选 G（14），到达终点。

最终最短路径权重为 14。

#Python 实现

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

#负权边问题

狄克斯特拉算法不能处理负权边。因为算法假设处理过的节点就是最短路径，但负权边可能使后续找到更短的路径，导致之前的假设不成立。

如果图中有负权边，应该使用贝尔曼-福特算法。

#时间复杂度

• 不优化：O(n²)
• 用堆优化：O(m + n log n)

#小结

• 狄克斯特拉算法每次选开销最小的节点处理，逐步确定最短路径
• 适用于加权图（无负权边），只适用于有向无环图（DAG）
• 不能处理负权边，有负权边用贝尔曼-福特
• 比贝尔曼-福特更高效