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

难度: Hard

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [from_i, to_i, edgeCost_i] 表示从 from_i 到 to_i 有一条代价为 edgeCost_i 的边。

请你实现一个 Graph 类：

Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径最小代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

示例 1：

输入：
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
输出：
[null, 6, -1, null, 6]

解释：
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
g.shortestPath(0, 3); // 返回 -1 。没有从 0 到 3 的路径。
g.addEdge([1, 3, 4]); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
g.shortestPath(0, 3); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。

提示：

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= from_i, to_i, from, to, node1, node2 <= n - 1
1 <= edgeCost_i, edgeCost <= 10⁶
图中任何时候都不会有重边和自环。
调用 addEdge 至多 100 次。
调用 shortestPath 至多 100 次。

Submission

运行时间: 237 ms

内存: 19.1 MB

class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.g = [[] * n for _ in range(n)] 
        for x, y, w in edges:
            self.g[x].append((y,w))

    def addEdge(self, e: List[int]) -> None:
        self.g[e[0]].append([e[1],e[2]])

    def shortestPath(self, start: int, end: int) -> int:
        n=len(self.g)
        dist=[inf]*n
        dist[start]=0
        heap=[(0,start)]

        while(heap):
            w0,y0=heappop(heap)
            if y0==end:return w0
            if w0>dist[y0]:continue
            for y,w in self.g[y0]:
                if dist[y0]+w<dist[y]:
                    dist[y]=w+dist[y0]
                    heappush(heap,(dist[y],y)) 
        return -1

Explain

The solution implements a graph class with methods to initialize the graph, add edges, and compute the shortest path between two nodes using Dijkstra's algorithm. The graph is represented as an adjacency list, where each node points to a list of tuples, each containing a connected node and the edge weight. The `addEdge` method appends a new edge to the adjacency list. The `shortestPath` method applies Dijkstra's algorithm using a priority queue (min-heap) to efficiently find the shortest path by continually expanding the least costly path until the destination is reached or all possible paths are considered.

时间复杂度: O(E log V)

空间复杂度: O(V + E)

class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        # Initialize an adjacency list for n nodes
        self.g = [[] for _ in range(n)]
        # Add existing edges to the graph
        for x, y, w in edges:
            self.g[x].append((y,w))

    def addEdge(self, e: List[int]) -> None:
        # Append a new edge to the adjacency list
        self.g[e[0]].append((e[1], e[2]))

    def shortestPath(self, start: int, end: int) -> int:
        n = len(self.g)
        dist = [float('inf')] * n
        dist[start] = 0
        heap = [(0, start)]
        # Dijkstra's algorithm using a priority queue
        while heap:
            w0, y0 = heappop(heap)
            # If the end node is reached, return the distance
            if y0 == end: return w0
            # Skip if a shorter path to y0 has been found
            if w0 > dist[y0]: continue
            # Relax edges
            for y, w in self.g[y0]:
                if dist[y0] + w < dist[y]:
                    dist[y] = w + dist[y0]
                    heappush(heap, (dist[y], y))
        return -1

Explore

在Dijkstra算法的标准实现中，不支持负权边。这是因为Dijkstra算法基于贪心策略，假设从源点出发到任何点的最短路径只会随着路径长度的增加而增加。如果存在负权边，就可能出现已经被确定为最短路径的点在未来被更新为更短的路径，这违背了Dijkstra算法的基本假设。若图中存在负权边，应使用其他算法，如Bellman-Ford算法，该算法可以处理负权边并能检测负权环。

优先队列（最小堆）是实现Dijkstra算法的理想数据结构，因为它可以保证每次从队列中提取出的都是当前未处理的最短路径的节点。这样可以有效地减少算法的运行时间，尤其是在处理大型图时更显著。如果使用普通队列，每次从队列中提取节点时都必须遍历整个队列以找到最短路径的节点，这会导致算法效率显著降低，使其从O((V+E)logV)增加到O(V^2)，其中V是顶点数，E是边数。

在`shortestPath`方法中，`dist[start] = 0`这一操作是初始化起点到自身的最短距离为0。这是因为从任何节点到自身的最短路径长度自然应该是0。这个初始化步骤是Dijkstra算法的一部分，确保算法开始时，起点的距离被正确设置，以便算法能从起点开始逐步计算到图中其他所有节点的最短路径。

在Dijkstra算法的实现中，`w0 > dist[y0]`的检查用来确定当前从优先队列中取出的路径是否仍然是有效的最短路径。由于算法中某个节点可能被多次添加到优先队列中（每次发现更短的路径时），最终从队列中取出的可能不是最短的那个。检查`w0 > dist[y0]`确保如果已经存在一个更短的路径到达该节点，则当前路径被忽略，这样可以避免不必要的计算和错误的路径更新。