动态规划法求单源最短路径问题

动态规划法可以用于解决单源最短路径问题，但是只适用于有向无环图（DAG）。对于一般的有向图，我们可以使用另一种算法——Dijkstra算法来解决单源最短路径问题。

Dijkstra算法的基本思想是：从源点开始，依次找到距离源点最近的未访问过的节点，并更新其邻居节点的距离。具体实现可以使用优先队列来维护未访问过的节点，每次从队列中取出距离源点最近的节点进行更新。

下面是使用Python实现Dijkstra算法的示例代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    
    # 初始化优先队列
    pq = [(0, start)]
    
    while pq:
        # 取出距离源点最近的节点
        (d, node) = heapq.heappop(pq)
        
        # 如果该节点已经访问过，则跳过
        if d > dist[node]:
            continue
        
        # 更新邻居节点的距离
        for neighbor, weight in graph[node].items():
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    
    return dist

其中，graph是一个字典，表示有向图的邻接表，start是源点。