算法简介

Dijkstra算法是一种用于计算加权图中单源最短路径的经典算法。通过逐步更新从起点到其他节点的距离，找到从起点到所有其他节点的最短路径。该算法最适用于非负权重的图。

思路流程

1. 初始化：
   为每个节点设置初始距离，起点的距离设为0，其他所有节点的距离设为无穷大。用一个列表记录所有未访问节点。
2. 选择当前节点：
   从未访问节点中选择当前距离最小的节点，并将其作为当前节点。如果当前节点的距离为无穷大，表示所有可达节点已遍历完，算法终止。
3. 更新邻居距离：
   对于当前节点的每个邻居，计算通过当前节点到达邻居节点的距离。如果该距离小于邻居节点当前的已知最短距离，则更新该邻居的最短距离和路径。
4. 重复：
   重复步骤2和3，直到所有节点都被访问。
5. 返回结果：
   最终得到从起点到所有其他节点的最短距离，以及每个节点的最短路径。

代码实现

# 邻接表，节点为字母，边的权重
graph = {
    'A': {'B': 6, 'C': 3},
    'B': {'A': 6, 'C': 2, 'D': 5},
    'C': {'A': 3, 'B': 2, 'D': 3, 'E': 4},
    'D': {'B': 5, 'C': 3, 'E': 2, 'F': 3},
    'E': {'C': 4, 'D': 2, 'F': 5},
    'F': {'D': 3, 'E': 5}
}

# Dijkstra算法
def dijkstra_naive(graph, start):
    # 初始化距离字典，使得所有节点距离初始化为无限大，起点距离为0
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    # 未访问节点的集合
    unvisited = list(graph.keys())
    # 用于存储最短路径的变量
    shortest_path = {node: None for node in graph}

    while unvisited:
        # 从未访问的节点中找到距离最小的节点
        current_node = min(unvisited, key=lambda node: distances[node])
        unvisited.remove(current_node)

        # 如果当前节点距离为无限大，说明剩下的节点无法到达，结束循环
        if distances[current_node] == float('infinity'):
            break

        # 遍历当前节点的邻居
        for neighbor, weight in graph[current_node].items():
            distance = distances[current_node] + weight
            # 如果找到更短的路径，更新距离和路径
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                shortest_path[neighbor] = current_node

    return distances, shortest_path

# 打印从A点到其他各点的最短路径和距离
def print_shortest_path(distances, shortest_path, start):
    for node, distance in distances.items():
        if node == start:
            continue
        path = []
        current_node = node
        while current_node:
            path.append(current_node)
            current_node = shortest_path[current_node]
        path = path[::-1]
        print(f"从 {start} 到 {node} 的最短路径: {' -> '.join(path)}, 距离: {distance}")

# 从A点开始计算
distances, shortest_path = dijkstra_naive(graph, 'A')
print_shortest_path(distances, shortest_path, 'A')

结果输出

根据Dijkstra算法的计算结果，从A点到其他各个点的最短路径和距离如下：

从 A 到 B 的最短路径: A -> C -> B, 距离: 5
从 A 到 C 的最短路径: A -> C, 距离: 3
从 A 到 D 的最短路径: A -> C -> D, 距离: 6
从 A 到 E 的最短路径: A -> C -> E, 距离: 7
从 A 到 F 的最短路径: A -> C -> D -> F, 距离: 9

总结

时间复杂度：使用最简单的朴素方法，时间复杂度为 O(n^2)，因为每次选择最小距离的节点需要遍历未访问的节点。
适用场景：适用于学习和理解算法流程的小规模图的计算。如果需要更高效的实现，可以使用优先队列（例如 heapq）来优化选择最小距离节点的步骤。

版权属于：Nan不南

本文链接：https://nfqqc.com/index.php/2025/03/20/82.html

转载时须注明出处及本声明