基于Dijsktra算法的最短路径求解

Dijkstra算法是一种贪心算法，用于求解带权有向图中从一个源点到其他所有点的最短路径。

算法步骤如下：

1. 初始化：将起点s加入集合S，将所有其他顶点加入集合T中。对于每个顶点v，如果存在一条边从s到v，则将该边的权值赋值给dist[v]，否则dist[v]赋值为无穷大。

2. 选择最小节点：在集合T中找到距离起点s最近的顶点u，并将其加入集合S。

3. 更新距离：对于集合T中的每个顶点v，如果存在一条从u到v的边，则计算新的距离d = dist[u] + w(u, v)。如果d小于dist[v]，则更新dist[v]的值。

4. 重复步骤2和3，直到集合T为空。

5. 最终结果：dist数组中保存了起点s到其他所有顶点的最短路径长度。

以下是一个基于Dijkstra算法的Python实现：

import heapq

def dijkstra(graph, start):
    # 初始化
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    queue = [(0, start)]
    
    while queue:
        # 选择最小节点
        (cost, node) = heapq.heappop(queue)
        
        # 更新距离
        if cost > dist[node]:
            continue
        for neighbor in graph[node]:
            new_cost = dist[node] + graph[node][neighbor]
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))
    
    return dist

其中，graph是一个字典，表示带权有向图。字典的键是图中的顶点，值是一个字典，表示从该顶点出发的边。每条边的键是目标顶点，值是边的权值。start是源点。