利用数据结构Dijkstra算法实现地铁网络最短路径的数据结构设计的关键代码

利用Dijkstra算法实现地铁网络最短路径的数据结构设计的关键代码如下：

# 定义地铁网络的节点类
class Node:
    def __init__(self, name):
        self.name = name
        self.neighbors = {}  # 存储相邻节点及对应的距离

    def add_neighbor(self, neighbor, distance):
        self.neighbors[neighbor] = distance

    def get_neighbors(self):
        return self.neighbors.keys()

    def get_distance(self, neighbor):
        return self.neighbors[neighbor]

# 定义地铁网络的图类
class SubwayNetwork:
    def __init__(self):
        self.nodes = {}  # 存储所有节点

    def add_node(self, node):
        self.nodes[node.name] = node

    def get_node(self, name):
        return self.nodes[name]

    def dijkstra(self, start_node, end_node):
        # 初始化距离字典，存储起点到各节点的最短距离
        distances = {node: float('inf') for node in self.nodes}
        distances[start_node] = 0

        # 初始化已访问节点集合和未访问节点集合
        visited = set()
        unvisited = set(self.nodes)

        while unvisited:
            # 选择当前距离最小的节点
            current_node = min(unvisited, key=lambda node: distances[node])

            # 更新当前节点的邻居节点的最短距离
            for neighbor in current_node.get_neighbors():
                new_distance = distances[current_node] + current_node.get_distance(neighbor)
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance

            # 将当前节点标记为已访问，并从未访问集合中移除
            visited.add(current_node)
            unvisited.remove(current_node)

            # 如果已经到达终点节点，则停止搜索
            if current_node == end_node:
                break

        return distances[end_node]

# 创建地铁网络图
subway = SubwayNetwork()

# 添加地铁站节点
station_a = Node("A")
station_b = Node("B")
station_c = Node("C")
station_d = Node("D")
station_e = Node("E")

# 添加地铁站之间的连接关系及距离
station_a.add_neighbor(station_b, 5)
station_a.add_neighbor(station_c, 3)
station_b.add_neighbor(station_d, 2)
station_c.add_neighbor(station_b, 1)
station_c.add_neighbor(station_d, 6)
station_d.add_neighbor(station_e, 4)

# 将节点添加到地铁网络图中
subway.add_node(station_a)
subway.add_node(station_b)
subway.add_node(station_c)
subway.add_node(station_d)
subway.add_node(station_e)

# 计算最短路径
start_station = station_a
end_station = station_e
shortest_distance = subway.dijkstra(start_station, end_station)

print(f"The shortest distance from {start_station.name} to {end_station.name} is {shortest_distance}")