3123. 在最短路径中找边

Hard

题目描述

给你一个有 n 个节点的无向加权图，节点编号从 0 到 n - 1。图由 m 条边组成，用二维数组 edges 表示，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条权重为 wi 的边。

考虑图中从节点 0 到节点 n - 1 的所有最短路径。你需要找到一个布尔数组 answer，其中 answer[i] 为 true 当且仅当边 edges[i] 是至少一条最短路径的一部分。否则，answer[i] 为 false。

返回数组 answer。

注意，图可能不是连通的。

示例 1：

输入：n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]

输出：[true,true,true,false,true,true,true,false]

解释：

以下是节点 0 和 5 之间的所有最短路径：

路径 0 -> 1 -> 5：权重之和为 4 + 1 = 5
路径 0 -> 2 -> 3 -> 5：权重之和为 1 + 1 + 3 = 5
路径 0 -> 2 -> 3 -> 1 -> 5：权重之和为 1 + 1 + 2 + 1 = 5

示例 2：

输入：n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]

输出：[true,false,false,true]

解释：

节点 0 和 3 之间有一条最短路径，即路径 0 -> 2 -> 3，权重之和为 1 + 2 = 3。

约束条件：

2 <= n <= 5 * 10^4
m == edges.length
1 <= m <= min(5 * 10^4, n * (n - 1) / 2)
0 <= ai, bi < n
ai != bi
1 <= wi <= 10^5
没有重复的边

解题思路

这道题需要判断每条边是否在从节点 0 到节点 n-1 的最短路径上。关键思路是使用 双向 Dijkstra 算法。

核心思路：

分别从节点 0 和节点 n-1 出发，使用 Dijkstra 算法计算到所有其他节点的最短距离
对于每条边 (u, v, w)，如果它在某条最短路径上，必须满足：
- dist_from_0[u] + w + dist_from_n1[v] == shortest_path 或
- dist_from_0[v] + w + dist_from_n1[u] == shortest_path

其中 shortest_path 是从节点 0 到节点 n-1 的最短路径长度。

算法步骤：

构建邻接表表示图
从节点 0 运行 Dijkstra，得到 dist_from_0[]
从节点 n-1 运行 Dijkstra，得到 dist_from_n1[]
计算最短路径长度 shortest_path = dist_from_0[n-1]
对每条边检查是否满足最短路径条件

这种方法的优势是只需要运行两次 Dijkstra，时间复杂度为 O((n+m)logn)，比枚举所有最短路径的方法更高效。

代码实现

class Solution {
public:
    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
        // 构建邻接表
        vector<vector<pair<int, int>>> graph(n);
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        
        // Dijkstra算法
        auto dijkstra = [&](int start) -> vector<long long> {
            vector<long long> dist(n, LLONG_MAX);
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
            dist[start] = 0;
            pq.push({0, start});
            
            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop();
                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 dist;
        };
        
        vector<long long> dist_from_0 = dijkstra(0);
        vector<long long> dist_from_n1 = dijkstra(n - 1);
        
        long long shortest_path = dist_from_0[n - 1];
        vector<bool> result(edges.size(), false);
        
        // 检查每条边是否在最短路径上
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            
            if (shortest_path != LLONG_MAX &&
                (dist_from_0[u] + w + dist_from_n1[v] == shortest_path ||
                 dist_from_0[v] + w + dist_from_n1[u] == shortest_path)) {
                result[i] = true;
            }
        }
        
        return result;
    }
};

class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        import heapq
        from collections import defaultdict
        
        # 构建邻接表
        graph = defaultdict(list)
        for i, (u, v, w) in enumerate(edges):
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        # Dijkstra算法
        def dijkstra(start):
            dist = [float('inf')] * n
            dist[start] = 0
            pq = [(0, start)]
            
            while pq:
                d, u = heapq.heappop(pq)
                if d > dist[u]:
                    continue
                
                for v, w in graph[u]:
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
                        heapq.heappush(pq, (dist[v], v))
            
            return dist
        
        dist_from_0 = dijkstra(0)
        dist_from_n1 = dijkstra(n - 1)
        
        shortest_path = dist_from_0[n - 1]
        result = []
        
        # 检查每条边是否在最短路径上
        for u, v, w in edges:
            if (shortest_path != float('inf') and
                (dist_from_0[u] + w + dist_from_n1[v] == shortest_path or
                 dist_from_0[v] + w + dist_from_n1[u] == shortest_path)):
                result.append(True)
            else:
                result.append(False)
        
        return result

public class Solution {
    public bool[] FindAnswer(int n, int[][] edges) {
        // 构建邻接表
        var graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        for (int i = 0; i < edges.Length; i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            graph[u].Add((v, w));
            graph[v].Add((u, w));
        }
        
        // Dijkstra算法
        long[] Dijkstra(int start) {
            var dist = new long[n];
            for (int i = 0; i < n; i++) dist[i] = long.MaxValue;
            dist[start] = 0;
            
            var pq = new PriorityQueue<int, long>();
            pq.Enqueue(start, 0);
            
            while (pq.Count > 0) {
                int u = pq.Dequeue();
                
                foreach (var (v, w) in graph[u]) {
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.Enqueue(v, dist[v]);
                    }
                }
            }
            return dist;
        }
        
        var distFrom0 = Dijkstra(0);
        var distFromN1 = Dijkstra(n - 1);
        
        long shortestPath = distFrom0[n - 1];
        var result = new bool[edges.Length];
        
        // 检查每条边是否在最短路径上
        for (int i = 0; i < edges.Length; i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            
            if (shortestPath != long.MaxValue &&
                (distFrom0[u] + w + distFromN1[v] == shortestPath ||
                 distFrom0[v] + w + distFromN1[u] == shortestPath)) {
                result[i] = true;
            }
        }
        
        return result;
    }
}

var findAnswer = function(n, edges) {
    const graph = Array(n).fill().map(() => []);
    
    for (let i = 0; i < edges.length; i++) {
        const [a, b, w] = edges[i];
        graph[a].push([b, w, i]);
        graph[b].push([a, w, i]);
    }
    
    const dijkstra = (start) => {
        const dist = Array(n).fill(Infinity);
        const pq = [[0, start]];
        dist[start] = 0;
        
        while (pq.length > 0) {
            pq.sort((a, b) => a[0] - b[0]);
            const [d, u] = pq.shift();
            
            if (d > dist[u]) continue;
            
            for (const [v, w, idx] of graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push([dist[v], v]);
                }
            }
        }
        
        return dist;
    };
    
    const distFrom0 = dijkstra(0);
    const distFromN1 = dijkstra(n - 1);
    
    const shortestPath = distFrom0[n - 1];
    const answer = Array(edges.length).fill(false);
    
    if (shortestPath === Infinity) return answer;
    
    for (let i = 0; i < edges.length; i++) {
        const [a, b, w] = edges[i];
        if (distFrom0[a] + w + distFromN1[b] === shortestPath || 
            distFrom0[b] + w + distFromN1[a] === shortestPath) {
            answer[i] = true;
        }
    }
    
    return answer;
};

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

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O((V + E) log V)	运行两次Dijkstra算法，其中V=n为节点数，E=m为边数
空间复杂度	O(V + E)	邻接表存储图结构和距离数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析