用Dijkstra算法求点V到其他顶点最短路径

Dijkstra算法是一种用于计算图中单源最短路径的经典算法。它可以找到从起始顶点到图中所有其他顶点的最短路径。以下是使用Dijkstra算法求点V到其他顶点最短路径的步骤：

1. **初始化**：
- 创建一个距离数组`dist[]`，用于存储从起点V到每个顶点的最短距离。初始时，将起点V的距离设为0，其他所有顶点的距离设为无穷大。
- 创建一个集合`S`，用于存储已确定最短路径的顶点。初始时，集合`S`为空。

2. **选择顶点**：
- 从未在集合`S`中的顶点中选择一个距离起点V最近的顶点u，将其加入集合`S`。

3. **更新距离**：
- 对于每个与顶点u相邻的顶点v，更新其距离`dist[v]`，如果通过u到达v的路径比当前已知的最短路径更短，则更新`dist[v]`为`dist[u] + 权重(u, v)`。

4. **重复步骤2和3**：
- 重复步骤2和3，直到所有顶点都在集合`S`中。

5. **结果**：
- 最终，距离数组`dist[]`中存储的就是从起点V到每个顶点的最短路径长度。

以下是一个简单的Python实现示例：

import heapq

def dijkstra(graph, start):
    # 初始化距离数组和优先队列
    dist = {vertex: float('infinity') for vertex in graph}
    dist[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_dist, current_vertex = heapq.heappop(priority_queue)
        
        # 如果当前距离大于已知最短距离，跳过
        if current_dist > dist[current_vertex]:
            continue
        
        # 遍历相邻顶点
        for neighbor, weight in graph[current_vertex].items():
            distance = current_dist + weight
            
            # 如果找到更短的路径，更新距离并加入优先队列
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return dist

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

# 计算从顶点 'A' 到其他顶点的最短路径
shortest_distances = dijkstra(graph, 'A')
print(shortest_distances)

这个示例中，我们定义了一个图`graph`，并使用Dijkstra算法计算从顶点'A'到其他顶点的最短路径。最终输出结果是一个字典，表示从起点到每个顶点的最短距离。