2642. 设计可以求最短路径的图类（Rating 1810）

以下内容偏向于记录个人练习过程及思考，请审慎阅读。

题目

2642. 设计可以求最短路径的图类

Rating 1810

思路

最短路板子题。Floyd 算法和 Dijkstra 算法都可以做。

代码

Floyd 算法

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        f = [[inf for _ in range(n)] for _ in range(n)] # 初始化节点间距离为无穷大
        for x in range(n):
            f[x][x] = 0 # 节点自己到自己的距离为0
        for x, y, w in edges:
            f[x][y] = w # 按照给定的边信息更新节点间距离
        # Floyd 算法更新 x 到 y 的最短距离
        for k in range(n):
            for x in range(n):
                for y in range(n):
                    f[x][y] = min(f[x][y], f[x][k] + f[k][y])
        self.n = n
        self.f = f


    def addEdge(self, edge: List[int]) -> None:
        f = self.f
        n = self.n
        x, y, w = edge
        for i in range(n):
            for j in range(n):
                f[i][j] = min(f[i][j], f[i][x] + w + f[y][j]) # 新增权重为w的x->y的边后，更新所有节点间的最短距离
        

    def shortestPath(self, node1: int, node2: int) -> int:
        return self.f[node1][node2] if self.f[node1][node2] != inf else -1

Dijkstra 算法（朴素）

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.g = [[] for _ in range(n)]
        for x, y, w in edges:
            self.g[x].append((y, w)) # 邻接表建图


    def addEdge(self, edge: List[int]) -> None:
        x, y, w = edge
        self.g[x].append((y, w)) # 更新邻接表  


    def shortestPath(self, node1: int, node2: int) -> int:
        n = len(self.g)
        dis = [inf for _ in range(n)]
        dis[node1] = 0
        vis = set()
        while True:
            x, dmin = -1, inf
            for y in range(n): # 找到不在vis中的且在dis里面最小的点及其距离
                if y not in vis and dis[y] < dmin:
                    x = y
                    dmin = dis[y]
            if x == -1: # 没找到，说明从node1开始的点都被更新过了
                return -1
            if x == node2: # 已经找到了最小值，返回答案
                return dmin
            vis.add(x) # 标记为找到了node1到x到最小值
            for y, w in self.g[x]: # 更新所有与x相连的点的距离
                if dmin + w < dis[y]:
                    dis[y] = dmin + w
        return -1

Dijkstra 算法（堆优化）

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.g = [[] for _ in range(n)]
        for x, y, w in edges:
            self.g[x].append((y, w)) # 邻接表建图


    def addEdge(self, edge: List[int]) -> None:
        x, y, w = edge
        self.g[x].append((y, w)) # 更新邻接表


    def shortestPath(self, node1: int, node2: int) -> int:
        n = len(self.g)
        dis = [inf for _ in range(n)]
        dis[node1] = 0
        hq = [(0, node1)] # 堆优化，用小顶堆，记录(dis, x)
        while hq:
            d, x = heappop(hq) # 堆中最小的距离和节点
            if d > dis[x]: # 堆中最小的距离比当前距离大，说明当前距离已经更新过了，跳过
                continue
            if x == node2: # 已经找到了最小值，返回答案
                return d
            for y, w in self.g[x]: # 更新所有与x相连的点的距离
                if d + w < dis[y]:
                    dis[y] = d + w
                    heappush(hq, (dis[y], y))
        return -1