python实现对有向图的代价一致搜索代码

Question

怎么样存储有向图，然后用代价一致算法求最优解，最后输出路径。这就是我遇到的疑问，希望各位可以帮我分析解决一下

Answer 1

引自免费微信小程序：皆我百晓生

在Python中，实现有向图的代价一致搜索（例如Dijkstra算法）通常涉及以下步骤：

1. 存储有向图：可以使用邻接列表或邻接矩阵来表示。这里我们使用邻接列表的方式，每个节点对应一个字典，键是可达的目标节点，值是对应的边的代价。

class Graph:
    def __init__(self):
        self.graph = {}  # 邻接列表

    def add_edge(self, start, end, cost):
        if start not in self.graph:
            self.graph[start] = {}
        self.graph[start][end] = cost

# 示例：
g = Graph()
g.add_edge('A', 'B', 3)
g.add_edge('A', 'C', 5)
g.add_edge('B', 'D', 1)
# ... 更多边

1. 实现Dijkstra算法：这个算法用于寻找从起点到所有其他点的最短路径。

import heapq

def dijkstra(graph, start_node):
    distances = {node: float('inf') for node in graph.graph.keys()}
    distances[start_node] = 0
    visited = set()

    priority_queue = [(0, start_node)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_node in visited:
            continue

        visited.add(current_node)

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

    return distances

# 示例：
start_node = 'A'
shortest_distances = dijkstra(g, start_node)
print(shortest_distances)  # 输出每个节点到起始节点A的最短距离

1. 输出路径：为了得到实际的路径而不是仅仅是最短距离，你可以在Dijkstra算法中同时维护一个父节点记录，以便于回溯生成路径。这里没有给出这部分代码，但原理是在更新每个节点的距离时，也保存其前驱节点信息，最后根据这些信息反向构造出最优路径。

以上给出了一个简单的Dijkstra算法实现框架，对于复杂场景可能需要适当调整以满足具体需求。