数据结构地铁线路最短路径实现

地铁线路最短路径问题可以使用图论中的最短路径算法来解决，常用的算法有Dijkstra算法和Floyd算法。

1. Dijkstra算法

Dijkstra算法是一种贪心算法，用于求解单源最短路径问题。具体实现步骤如下：

- 创建一个距离数组dist[]用于保存起点s到各个点的最短距离，将起点s的距离设为0，其余点的距离设为无穷大。
- 创建一个已访问数组visited[]，初始时所有元素都为false，表示所有点均未被访问过。
- 重复以下步骤，直到所有点都被访问过：

- 从未访问过的点中选择距离起点s最近的点u，将其标记为已访问。
- 对于u的所有相邻节点v，如果从起点s到v的距离比当前dist[v]更短，则更新dist[v]为新距离。

实现代码如下：

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    visited = [False] * n
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        (d, u) = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

其中graph是邻接表表示的图，start是起点。

2. Floyd算法

Floyd算法是一种动态规划算法，用于求解所有点对之间的最短路径。具体实现步骤如下：

- 创建一个距离矩阵dist[]，其中dist[i][j]表示从节点i到节点j的最短距离，初始化为邻接矩阵。
- 重复以下操作，k表示中间节点：

- 对于每对节点i和j，如果通过节点k可以使得从i到j的距离更短，则更新dist[i][j]为新距离。

实现代码如下：

def floyd(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        for j, w in graph[i]:
            dist[i][j] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

其中graph是邻接表表示的图。