D
DevExCode

LeetCode 3123: Find Edges in Shortest Paths Solution

Master LeetCode problem 3123 (Find Edges in Shortest Paths), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use Dijkstra's algorithm to find the shortest paths from node 0 to all other nodes in the graph. Then, we iterate through the edges and check if removing the edge would increase the shortest path distance between node 0 and node n-1. If removing the edge increases the shortest path distance, it means the edge is part of at least one shortest path.

  1. Apply Dijkstra's algorithm to find the shortest paths from node 0 to all other nodes.
  2. Iterate through each edge and check if removing the edge increases the shortest path distance between node 0 and node n-1.
  3. Create a boolean array to store whether each edge is part of at least one shortest path.

Time Complexity: O(m log n) where m is the number of edges and n is the number of nodes.

Space Complexity: O(n) for the priority queue and O(m) for the boolean array.

:

Solution Code

class Solution {
    public List<Boolean> findEdgeShortestPaths(int n, int[][] edges) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new HashMap<>()).put(edge[1], edge[2]);
            graph.computeIfAbsent(edge[1], k -> new HashMap<>()).put(edge[0], edge[2]);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[]{0, 0});

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int node = curr[0];
            int distance = curr[1];
            if (dist[node] < distance) continue;

            for (int neighbor : graph.getOrDefault(node, new HashMap<>()).keySet()) {
                int newDist = distance + graph.get(node).get(neighbor);
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.offer(new int[]{neighbor, newDist});
                }
            }
        }

        List<Boolean> result = new ArrayList<>();
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            if (dist[u] + weight == dist[v] || dist[v] + weight == dist[u]) {
                result.add(true);
            } else {
                result.add(false);
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 3123 (Find Edges in Shortest Paths)?

This page provides optimized solutions for LeetCode problem 3123 (Find Edges in Shortest Paths) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3123 (Find Edges in Shortest Paths)?

The time complexity for LeetCode 3123 (Find Edges in Shortest Paths) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3123 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3123 in Java, C++, or Python.

Back to LeetCode Solutions