贪心算法在 Dijkstra 算法中的妙用：求解最短路径的利器

# 1. 贪心算法概述

贪心算法是一种启发式算法，它通过在每个步骤中做出局部最优选择，来逐步求解问题。贪心算法的思想是：在当前情况下，做出最有利于全局最优解的选择，而不考虑未来可能的后果。

贪心算法的特点包括：

- **局部最优：**贪心算法在每个步骤中做出局部最优选择，而不是全局最优选择。
- **简单性：**贪心算法通常易于理解和实现。
- **不保证最优解：**贪心算法不能保证找到全局最优解，但通常可以找到近似最优解。

# 2. Dijkstra 算法原理与实现

### 2.1 Dijkstra 算法的原理

#### 2.1.1 算法的思想和步骤

Dijkstra 算法是一种贪心算法，用于解决单源最短路径问题。其基本思想是：从源点出发，依次选择当前已知最短路径上距离源点最小的未访问节点，将其加入已访问节点集合，并更新其他节点到源点的最短路径。

算法的具体步骤如下：

1. 初始化：将源点到所有其他节点的距离设为无穷大，源点到自身的距离设为 0。
2. 选择：从未访问的节点中选择距离源点最小的节点。
3. 标记：将选择的节点标记为已访问。
4. 更新：对于已访问节点的相邻节点，如果经过已访问节点到相邻节点的距离小于当前已知最短路径，则更新相邻节点到源点的最短路径。
5. 重复：重复步骤 2-4，直到所有节点都已访问。

#### 2.1.2 算法的复杂度分析

Dijkstra 算法的时间复杂度为 O(V^2)，其中 V 是图中的节点数。这是因为算法需要遍历所有节点，并在每次遍历中更新所有节点到源点的最短路径。

### 2.2 Dijkstra 算法的实现

#### 2.2.1 伪代码描述

function Dijkstra(graph, source):
    dist[source] = 0                      // 初始化源点到自身的距离为 0
    for each vertex v in graph:
        if v != source:
            dist[v] = infinity            // 初始化其他节点到源点的距离为无穷大
    while unvisited set is not empty:
        v = vertex in unvisited set with minimum dist[v]
        for each neighbor u of v:
            alt = dist[v] + weight(v, u)
            if alt < dist[u]:
                dist[u] = alt            // 更新 u 到源点的最短路径
    return dist

#### 2.2.2 代码实现示例

import heapq

def Dijkstra(graph, source):
    """
    Dijkstra 算法求单源最短路径

    Args:
        graph: 图的邻接表表示
        source: 源点

    Returns:
        dist: 源点到所有其他节点的最短路径距离
    """

    # 初始化距离表
    dist = {v: float('inf') for v in graph}
    dist[source] = 0

    # 初始化优先队列
    pq = [(0, source)]

    while pq:
        # 获取当前距离源点最小的节点
        current_dist, current_node = heapq.heappop(pq)

        # 如果当前节点到源点的距离大于已知的最小距离，则跳过
        if current_dist > dist[current_node]:
            continue

        # 遍历当前节点的相邻节点
        for neighbor, weight in graph[current_node].items():
            # 计算经过当前节点到相邻节点的距离
            alt = current_dist + weight

            # 如果经过当前节点到相邻节点的距离小于已知的最小距离，则更新相邻节点到源点的距离
            if alt < dist[neighbor]:
                dist[neighbor] = alt
                heapq.heappush(pq, (alt, neighbor))

    return dist

# 3. 贪心算法在 Dijkstra 算法中的应用

### 3.1 贪心算法的思想

#### 3.1.1 贪心算法的定义和特点

贪心算法是一种启发式算法，它通过在每一步中做出局部最优的选择，来解决优化问题。其主要特点如下：

- **局部最优性：**贪