4 Dijkstra算法与A*算法深入解析

在算法的世界中，图算法的应用场景广泛，尤其是在路径寻找和优化问题中。在上一篇教程中，我们探讨了高级排序算法的比较，而在本篇中，我们将深入分析两种图算法：Dijkstra算法与A*算法。这两个算法都是为了寻找图中两点之间的最短路径，但它们的实现机制和适用场景有所不同。

Dijkstra算法

Dijkstra算法是一种贪心算法，旨在找到从起始节点到其他所有节点的最短路径。它的基本思想是每次选择当前已知最短路径的节点来扩展，从而逐步发现最短路径。

算法步骤

1. 初始化：设置起始节点的距离为0，其他节点的距离为无穷大。
2. 将所有节点标记为未访问。
3. 在未访问的节点中选择距离起始节点最近的节点u。
4. 对于每一个与u相邻的节点v，计算从起始节点到v的距离。如果通过u到达v的距离更短，则更新v的距离。
5. 标记节点u为已访问。
6. 重复步骤3到5，直到所有节点都被访问或找到目标节点。

复杂度

Dijkstra算法的时间复杂度为$O((V + E) \log V)$，其中$V$是图中的节点数，$E$是边数。使用优先队列（如最小堆）可以有效地提高性能。

案例分析

考虑一个简单的图：

    1
(A)----(B)
 | \    |
4|  \2  |1
 |   \  |
(C)----(D)
    3

我们要从节点A找到到节点D的最短路径。

1. 初始化：d(A) = 0, d(B) = ∞, d(C) = ∞, d(D) = ∞.
2. 选择A，距离更新：
   • d(B) = min(∞, 0 + 1) = 1
   • d(C) = min(∞, 0 + 4) = 4
3. 选择B，距离更新：
   • d(D) = min(∞, 1 + 1) = 2
4. 选择D，没有相邻未访问节点；结束。
5. 最短路径为A -> B -> D，总距离为2。

Python代码实现

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_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
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 1},
    'C': {'A': 4, 'D': 3},
    'D': {'B': 1, 'C': 3}
}

print(dijkstra(graph, 'A'))  # 输出从A到各点的最短距离

A*算法

A*算法是一种启发式搜索算法，它结合了Dijkstra算法的优点，并引入了启发式方法来优化路径搜索。通过使用一个启发式函数，它可以更快速地找到最优路径。

启发式函数

启发式函数通常是一个估计函数，能够预测到目标节点的最短距离。常用的启发式函数是曼哈顿距离或欧几里得距离，具体取决于问题的性质。

算法步骤

1. 初始化：设置起始节点的g（到当前节点的成本）和f（预测成本g + h）。
2. 维护一个打开列表（待扩展节点）和关闭列表（已扩展节点）。
3. 在打开列表中选择f值最低的节点并扩展。
4. 对于当前节点的每个相邻节点，计算其g、h和f值，并根据规则更新打开列表。
5. 重复步骤3和4，直至找到目标节点或打开列表为空。

案例分析

假设我们使用上述图形，但引入一个目标节点D:

1. A的g = 0，h(D) = 2（估计到达D的距离），f = 0 + 2 = 2。
2. 扩展节点A，更新相邻节点B和C的值：
   • 对于B，g = 1, h(D) = 1, f = 1 + 1 = 2。
   • 对于C，g = 4, h(D) = 3, f = 4 + 3 = 7。
3. 选择B，扩展至D，更新路径，直到找到目标。

Python代码实现

def heuristic(a, b):
    # 曼哈顿距离作为启发式函数
    return abs(ord(a) - ord(b))

def a_star(graph, start, goal):
    open_list = []
    closed_set = set()
    g_score = {vertex: float('infinity') for vertex in graph}
    g_score[start] = 0
    f_score = {vertex: float('infinity') for vertex in graph}
    f_score[start] = heuristic(start, goal)
    heapq.heappush(open_list, (f_score[start], start))

    while open_list:
        current = heapq.heappop(open_list)[1]

        if current == goal:
            return g_score[current]  # 返回目标的g值，代表最短路径

        closed_set.add(current)

        for neighbor, weight in graph[current].items():
            if neighbor in closed_set:
                continue
            
            tentative_g_score = g_score[current] + weight

            if tentative_g_score < g_score[neighbor]:
                g_score[neighbor] = tentative_g