2642. 设计图的最短路径计算器

Hard

题目描述

有一个由 n 个节点组成的有向加权图，节点编号为 0 到 n - 1。图的边最初由给定的数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条权重为 edgeCosti 的边。

实现 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 <= fromi, toi, from, to, node1, node2 <= n - 1
1 <= edgeCosti, edgeCost <= 10^6
在任何时候，图中都没有重复的边和自环。
addEdge 最多被调用 100 次。
shortestPath 最多被调用 100 次。

解题思路

这道题要求我们设计一个图类，支持动态添加边和查询最短路径。主要有两种解法：

解法一：每次查询时使用 Dijkstra 算法

用邻接表存储图
每次调用 shortestPath 时运行 Dijkstra 算法
时间复杂度：每次查询 O((V+E)logV)

解法二：预计算所有点对的最短距离（Floyd-Warshall）

维护一个距离矩阵
每次添加边后更新矩阵
查询时直接返回结果

由于题目约束中 n <= 100，且查询和添加边的次数都不多，两种解法都可行。但考虑到添加边后需要重新计算的开销，推荐使用解法一，即每次查询时使用 Dijkstra 算法。

Dijkstra 算法使用优先队列（最小堆）来维护当前距离最小的节点，逐步扩展到所有可达节点。当找到目标节点时立即返回距离，如果遍历完所有可达节点都没找到目标，则返回 -1。

实现要点：

用邻接表存储图的边
Dijkstra 算法中使用优先队列优化
维护距离数组记录到各节点的最短距离
添加边时直接在邻接表中插入新边

代码实现

class Graph {
private:
    int n;
    vector<vector<pair<int, int>>> graph;
    
public:
    Graph(int n, vector<vector<int>>& edges) : n(n), graph(n) {
        for (auto& edge : edges) {
            graph[edge[0]].push_back({edge[1], edge[2]});
        }
    }
    
    void addEdge(vector<int> edge) {
        graph[edge[0]].push_back({edge[1], edge[2]});
    }
    
    int shortestPath(int node1, int node2) {
        if (node1 == node2) return 0;
        
        vector<int> dist(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[node1] = 0;
        pq.push({0, node1});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (u == node2) return d;
            if (d > dist[u]) continue;
            
            for (auto [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return -1;
    }
};

import heapq
from typing import List

class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for u, v, w in edges:
            self.graph[u].append((v, w))
    
    def addEdge(self, edge: List[int]) -> None:
        u, v, w = edge
        self.graph[u].append((v, w))
    
    def shortestPath(self, node1: int, node2: int) -> int:
        if node1 == node2:
            return 0
        
        dist = [float('inf')] * self.n
        heap = [(0, node1)]
        dist[node1] = 0
        
        while heap:
            d, u = heapq.heappop(heap)
            
            if u == node2:
                return d
            
            if d > dist[u]:
                continue
            
            for v, w in self.graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(heap, (dist[v], v))
        
        return -1

using System;
using System.Collections.Generic;

public class Graph {
    private int n;
    private List<(int, int)>[] graph;
    
    public Graph(int n, int[][] edges) {
        this.n = n;
        this.graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            this.graph[i] = new List<(int, int)>();
        }
        
        foreach (var edge in edges) {
            this.graph[edge[0]].Add((edge[1], edge[2]));
        }
    }
    
    public void AddEdge(int[] edge) {
        this.graph[edge[0]].Add((edge[1], edge[2]));
    }
    
    public int ShortestPath(int node1, int node2) {
        if (node1 == node2) return 0;
        
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        
        var pq = new PriorityQueue<(int dist, int node), int>();
        dist[node1] = 0;
        pq.Enqueue((0, node1), 0);
        
        while (pq.Count > 0) {
            var (d, u) = pq.Dequeue();
            
            if (u == node2) return d;
            if (d > dist[u]) continue;
            
            foreach (var (v, w) in graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.Enqueue((dist[v], v), dist[v]);
                }
            }
        }
        
        return -1;
    }
}

var Graph = function(n, edges) {
    this.n = n;
    this.dist = Array(n).fill().map(() => Array(n).fill(Infinity));
    
    for (let i = 0; i < n; i++) {
        this.dist[i][i] = 0;
    }
    
    for (let [from, to, cost] of edges) {
        this.dist[from][to] = cost;
    }
    
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (this.dist[i][k] + this.dist[k][j] < this.dist[i][j]) {
                    this.dist[i][j] = this.dist[i][k] + this.dist[k][j];
                }
            }
        }
    }
};

Graph.prototype.addEdge = function(edge) {
    let [from, to, cost] = edge;
    this.dist[from][to] = cost;
    
    for (let i = 0; i < this.n; i++) {
        for (let j = 0; j < this.n; j++) {
            if (this.dist[i][from] + cost + this.dist[to][j] < this.dist[i][j]) {
                this.dist[i][j] = this.dist[i][from] + cost + this.dist[to][j];
            }
        }
    }
};

Graph.prototype.shortestPath = function(node1, node2) {
    return this.dist[node1][node2] === Infinity ? -1 : this.dist[node1][node2];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(E)	O(V + E)
addEdge	O(1)	O(1)
shortestPath	O((V + E) log V)	O(V)

其中 V 是节点数，E 是边数。每次查询最短路径使用 Dijkstra 算法，时间复杂度为 O((V + E) log V)。

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

解题思路

代码实现

复杂度分析

相关题目