最短路径算法有哪些？Dijkstra算法实现-js教程-PHP中文网

最短路径算法有哪些？Dijkstra算法实现

月夜之吻

发布： 2025-08-20 13:34:01

原创

768人浏览过

Dijkstra算法用于寻找加权图中单源最短路径，其核心是贪心策略，通过维护距离数组和优先队列逐步确定最短路径，每次选择距离起点最近的未访问顶点并更新其邻居的距离，直到所有顶点都被访问。该算法无法处理负权边，因贪心策略可能导致错误的最短路径判断。对于含负权边的图，应使用Bellman-Ford算法；若需计算所有顶点间的最短路径，可采用Floyd-Warshall算法；而A*算法则适用于有启发信息的场景。Dijkstra算法的性能依赖于优先队列的实现方式：使用数组时时间复杂度为O(V²)，二叉堆为O(E log V)，斐波那契堆可达O(E + V log V)，在实际应用中常借助Python的heapq模块实现高效版本。

最短路径算法有哪些？dijkstra算法实现

寻找最短路径，就像在迷宫中找出口一样，有各种不同的方法。Dijkstra算法是其中一种常用的，它能帮你找到从一个起点到其他所有点的最短距离。

解决方案：

Dijkstra算法是一种贪心算法，用于在加权图中寻找单源最短路径。它的基本思想是：维护一个已找到最短路径的顶点集合，以及一个未找到最短路径的顶点集合。每次从未找到最短路径的顶点中，选择距离起点最近的顶点，将其加入已找到最短路径的顶点集合，并更新起点到其他未找到最短路径的顶点的距离。

简单来说，就像是逐步扩张一个“安全区”，安全区内的点到起点的距离都是已知的最短距离，然后每次从安全区外选择一个离安全区最近的点加入安全区，直到所有点都加入安全区为止。

Dijkstra算法的实现步骤如下：

初始化：
- 创建一个距离数组
  dist[]
  登录后复制
  登录后复制
  登录后复制
  ，用于存储起点到每个顶点的距离。初始时，起点到自身的距离为0，到其他顶点的距离为无穷大。
- 创建一个集合
```
visited[]
```
  登录后复制
  ，用于标记顶点是否已被访问。初始时，所有顶点都未被访问。
循环：
- 从
  dist[]
  登录后复制
  登录后复制
  登录后复制
  中选择一个未被访问的，且距离起点最近的顶点
  u
  登录后复制
  登录后复制
  登录后复制
  登录后复制
  。
- 将顶点
  u
  登录后复制
  登录后复制
  登录后复制
  登录后复制
  标记为已访问。
- 对于顶点
  u
  登录后复制
  登录后复制
  登录后复制
  登录后复制
  的每个邻接顶点
```
v
```
  登录后复制
  登录后复制
  ，如果
```
dist[v] > dist[u] + weight(u, v)
```
  登录后复制
  ，则更新
```
dist[v] = dist[u] + weight(u, v)
```
  登录后复制
  ，其中
```
weight(u, v)
```
  登录后复制
  表示顶点
  u
  登录后复制
  登录后复制
  登录后复制
  登录后复制
  到顶点
```
v
```
  登录后复制
  登录后复制
  的边的权重。
重复步骤2，直到所有顶点都被访问，或者
```
dist[]
```
登录后复制
登录后复制
登录后复制
中所有未被访问的顶点距离起点都是无穷大。

下面是一个Dijkstra算法的Python实现示例：

import heapq

def dijkstra(graph, start):
    """
    使用Dijkstra算法计算从start节点到图中所有其他节点的最短路径。

    Args:
        graph: 一个字典，表示图的邻接列表。键是节点，值是 (邻居节点, 权重) 的列表。
        start: 起始节点。

    Returns:
        一个字典，键是节点，值是从起始节点到该节点的最短距离。如果节点不可达，则距离为无穷大。
    """

    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]  # (距离, 节点)

    while priority_queue:
        dist, current_node = heapq.heappop(priority_queue)

        if dist > distances[current_node]:
            continue  # 已经找到更短的路径

        for neighbor, weight in graph[current_node]:
            distance = dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 示例图
graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('A', 5), ('C', 2), ('D', 1)],
    'C': [('A', 1), ('B', 2), ('D', 4), ('E', 8)],
    'D': [('B', 1), ('C', 4), ('E', 3), ('F', 6)],
    'E': [('C', 8), ('D', 3), ('F', 2)],
    'F': [('D', 6), ('E', 2)]
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

print(f"从节点 {start_node} 到其他节点的最短路径：")
for node, distance in shortest_paths.items():
    print(f"到节点 {node} 的距离: {distance}")

登录后复制