动态规划法求多段图最短路径python代码实例

动态规划法通常用于解决最优化问题，如最短路径问题，在多段图（有向无环图DAG）中也适用。这里我们通过Python实现Dijkstra算法的改进版，适用于多源最短路径问题（所有节点到其他所有节点的最短路径），它结合了广度优先搜索(BFS)和动态规划的思想。

首先，我们需要创建邻接表表示多段图，并使用优先队列（可以用heapq模块的`PriorityQueue`实现）辅助查找最小距离节点。

以下是简单的Python代码示例：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue  # 如果当前距离更大，跳过

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 示例多段图的邻接表表示
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'D': 2},
    'C': {'D': 3},
    'D': {}
}

# 求从每个节点到其他所有节点的最短路径
shortest_paths = {}
for node in graph:
    shortest_paths[node] = dijkstra(graph, node)

print(shortest_paths)

在这个例子中，`dijkstra` 函数接受一个邻接表和起点，然后返回从起点到图中所有其他节点的最短路径。注意这个代码仅适用于无负权边的图。