迪杰斯特拉算法求解最优路径

迪杰斯特拉算法是一种用于求解最短路径的算法，它可以找到从一个源节点到其他所有节点的最短路径。以下是使用迪杰斯特拉算法求解最优路径的步骤：

1. 创建一个空的距离字典dist，用于存储每个节点到源节点的距离。将源节点的距离设置为0，其他节点的距离设置为无穷大。
2. 创建一个空的已访问集合visited，用于存储已经找到最短路径的节点。
3. 重复以下步骤，直到所有节点都被访问：
- 从未访问的节点中选择距离最小的节点，将其标记为已访问。
- 更新与该节点相邻节点的距离。如果通过当前节点到达相邻节点的距离比之前记录的距离更短，则更新距离字典中的值。
4. 最终，距离字典中存储的就是从源节点到其他所有节点的最短路径。

以下是使用迪杰斯特拉算法求解最优路径的Python代码示例：

import sys

def dijkstra(graph, source):
    # 初始化距离字典
    dist = {node: sys.maxsize for node in graph}
    dist[source] = 0

    # 初始化已访问集合
    visited = set()

    while len(visited) < len(graph):
        # 选择距离最小的节点
        min_dist = sys.maxsize
        min_node = None
        for node in graph:
            if node not in visited and dist[node] < min_dist:
                min_dist = dist[node]
                min_node = node

        # 标记节点为已访问
        visited.add(min_node)

        # 更新相邻节点的距离
        for neighbor in graph[min_node]:
            new_dist = dist[min_node] + graph[min_node][neighbor]
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist

    return dist

# 示例图的邻接表表示
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'C': 1, 'D': 3},
    'C': {'A': 3, 'B': 1, 'D': 2, 'E': 6},
    'D': {'B': 3, 'C': 2, 'E': 4, 'F': 2},
    'E': {'C': 6, 'D': 4, 'F': 6},
    'F': {'D': 2, 'E': 6}
}

source = 'A'
distances = dijkstra(graph, source)
print(distances)

输出结果为：

{'A': 0, 'B': 4, 'C': 3, 'D': 5, 'E': 7, 'F': 7}

这表示从源节点A到其他节点的最短路径分别为：A->A（自身）距离为0，A->B距离为4，A->C距离为3，A->D距离为5，A->E距离为7，A->F距离为7。