Facebook Pixel

3123. Find Edges in Shortest Paths

HardDepth-First SearchBreadth-First SearchGraphShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an undirected weighted graph of n nodes numbered from 0 to n - 1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [a_i, b_i, w_i] indicates that there is an edge between nodes a_i and b_i with weight w_i.

Your task is to consider all the shortest paths from node 0 to node n - 1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false.

Note that the graph may not be connected.

Intuition

To solve this problem, the first step is to compute the shortest paths from node 0 to all other nodes. Dijkstra's algorithm is well-suited for this task due to its efficiency with positive weights. By finding the shortest path distances, we can determine the minimum possible weight to reach each node.

Once we have the shortest distances, the second step involves tracing back from node n-1 to node 0. We explore each edge (a, b, w) to check if dist[a] == dist[b] + w. If this condition holds, it means that edge is part of a shortest path and should be marked as true in our answer array.

By using a priority queue (to utilize Dijkstra's algorithm) and a deque for tracing back the path, the algorithm efficiently checks each edge's involvement in the shortest path, ensuring an optimal solution.

Learn more about Depth-First Search, Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution utilizes Dijkstra's algorithm to determine the shortest paths. Here's a detailed breakdown of the implementation:

  1. Graph Representation:
    The graph is represented as an adjacency list using a dictionary of lists, g. Each entry in the list contains a tuple with the neighboring node, the edge weight, and the edge index:

    g[a].append((b, w, i))

  2. Shortest Path Computation:
    We initialize an array dist to hold the shortest distance from node 0 to every other node, setting dist[0] = 0 and all others to infinity (inf). A priority queue (min-heap), q, is used to efficiently fetch the next closest node to expand:

    dist = [inf] * n
dist[0] = 0
q = [(0, 0)]

    The core of Dijkstra's algorithm involves:

    • Extracting the node a with the smallest current distance da through heappop.
    • For each neighboring node b of a, updating the shortest path distance if a shorter path is found through a: 
      if dist[b] > dist[a] + w:
    dist[b] = dist[a] + w
    heappush(q, (dist[b], b))

  3. Trace Back the Shortest Path:
    With the shortest distances determined, we now create the boolean answer array initially filled with False. If the distance to node n-1 is infinity, the nodes are disconnected, and we return answer. Otherwise, using a deque, the algorithm traverses backward from node n-1, verifying edges that contribute to the shortest path:

    if dist[a] == dist[b] + w:
    ans[i] = True
    q.append(b)

  4. Final Return:
    After identifying relevant edges, the answer array is returned, marking True for edges that are part of at least one shortest path from node 0 to node n-1.

This approach ensures that all shortest paths are considered and marked accurately in a time-efficient manner.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a simple example to illustrate the solution approach.

Example Graph

Consider a graph with 4 nodes and the following edges:

  • edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 2, 2], [1, 3, 4]]

The graph looks like this:

0 --1-- 1 --1-- 2 --1-- 3
 \      |      /
  \     |     /
   --2--     /
  (Edge 3)  /

Step 1: Graph Representation

We represent this graph as an adjacency list:

  • g[0] = [(1, 1, 0), (2, 2, 3)]
  • g[1] = [(2, 1, 1), (3, 4, 4)]
  • g[2] = [(3, 1, 2)]

Step 2: Compute Shortest Paths (Dijkstra's Algorithm)

  1. Initialize dist = [0, inf, inf, inf] and q = [(0, 0)].
  2. Pop (0, 0) from q, inspect edges [0, 1, 1] and [0, 2, 2]:
    • Update dist[1] = 1 and push (1, 1) onto q.
    • Update dist[2] = 2 and push (2, 2) onto q.
  3. Pop (1, 1) from q, inspect edges [1, 2, 1] and [1, 3, 4]:
    • Update dist[2] isn't needed as it is already 2.
    • Update dist[3] = 5 and push (5, 3) onto q.
  4. Pop (2, 2) from q, inspect edge [2, 3, 1]:
    • Update dist[3] = 3 and push (3, 3) onto q.
  5. Now dist = [0, 1, 2, 3].

Step 3: Trace Back the Shortest Path

Initialize answer = [False, False, False, False, False] and start from node n-1 = 3.

  1. From node 3, check incoming edges:

    • [2, 3, 1] is valid as dist[2] + 1 = dist[3], mark answer[2] as True.
    • Add node 2 to the deque.

  2. From node 2, check incoming edges:

    • [0, 2, 2] is valid as dist[0] + 2 = dist[2], mark answer[3] as True.
    • Add node 0 to the deque.

  3. At this point, there are no valid edges for node 0 in the path that reaches 3, so stop tracing.

Final Answer

The answer array after tracing the shortest paths will be:

answer = [False, False, True, True, False]

This indicates that edges [2, 3, 1] and [0, 2, 2] are part of at least one shortest path from node 0 to node n - 1.

Solution Implementation

1from collections import defaultdict, deque
2from heapq import heappop, heappush
3from typing import List
4from math import inf
5
6class Solution:
7    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
8        # Create graph as an adjacency list with edge index and weight
9        graph = defaultdict(list)
10        for index, (source, destination, weight) in enumerate(edges):
11            graph[source].append((destination, weight, index))
12            graph[destination].append((source, weight, index))
13      
14        # Initialize distance array with infinity, set starting node distance to 0
15        dist = [inf] * n
16        dist[0] = 0
17
18        # Min-heap (priority queue) to store (distance, node)
19        min_heap = [(0, 0)]
20
21        # Dijkstra's algorithm to find shortest paths
22        while min_heap:
23            current_distance, current_node = heappop(min_heap)
24            if current_distance > dist[current_node]:
25                continue
26            for neighbor, weight, _ in graph[current_node]:
27                if dist[neighbor] > dist[current_node] + weight:
28                    dist[neighbor] = dist[current_node] + weight
29                    heappush(min_heap, (dist[neighbor], neighbor))
30      
31        # If there's no path to the last node
32        result_length = len(edges)
33        answer = [False] * result_length
34        if dist[n - 1] == inf:
35            return answer
36
37        # Traverse from end node and mark edges part of shortest paths
38        queue = deque([n - 1])
39        while queue:
40            node = queue.popleft()
41            for neighbor, weight, index in graph[node]:
42                if dist[node] == dist[neighbor] + weight:
43                    answer[index] = True
44                    queue.append(neighbor)
45      
46        return answer
47
1import java.util.*;
2
3class Solution {
4    public boolean[] findAnswer(int n, int[][] edges) {
5        // Initialize adjacency list to store the graph
6        List<int[]>[] graph = new List[n];
7        Arrays.setAll(graph, k -> new ArrayList<>());
8
9        int edgesCount = edges.length;
10      
11        // Populate the graph with edges
12        for (int i = 0; i < edgesCount; ++i) {
13            int start = edges[i][0];
14            int end = edges[i][1];
15            int weight = edges[i][2];
16            graph[start].add(new int[] {end, weight, i});
17            graph[end].add(new int[] {start, weight, i});
18        }
19
20        // Initialize distances array with infinity
21        int[] distances = new int[n];
22        final int INF = 1 << 30;
23        Arrays.fill(distances, INF);
24        distances[0] = 0;
25
26        // Priority queue to implement Dijkstra's algorithm
27        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
28        priorityQueue.offer(new int[] {0, 0});
29
30        // Perform Dijkstra's algorithm
31        while (!priorityQueue.isEmpty()) {
32            int[] current = priorityQueue.poll();
33            int currentDistance = current[0];
34            int currentNode = current[1];
35          
36            if (currentDistance > distances[currentNode]) {
37                continue;
38            }
39
40            // Relaxation step
41            for (var edge : graph[currentNode]) {
42                int neighbor = edge[0];
43                int weight = edge[1];
44                if (distances[neighbor] > distances[currentNode] + weight) {
45                    distances[neighbor] = distances[currentNode] + weight;
46                    priorityQueue.offer(new int[] {distances[neighbor], neighbor});
47                }
48            }
49        }
50
51        // Initialize answer array
52        boolean[] answer = new boolean[edgesCount];
53      
54        // If there is no path to the last node
55        if (distances[n - 1] == INF) {
56            return answer;
57        }
58
59        // Queue for tracking edges that are part of the shortest path
60        Deque<Integer> queue = new ArrayDeque<>();
61        queue.offer(n - 1);
62
63        // Traverse the shortest path in reverse
64        while (!queue.isEmpty()) {
65            int currentNode = queue.poll();
66          
67            for (var edge : graph[currentNode]) {
68                int neighbor = edge[0];
69                int weight = edge[1];
70                int edgeIndex = edge[2];
71              
72                if (distances[currentNode] == distances[neighbor] + weight) {
73                    answer[edgeIndex] = true;
74                    queue.offer(neighbor);
75                }
76            }
77        }
78        return answer;
79    }
80}
81
1class Solution {
2public:
3    vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
4        // Graph represented as an adjacency list with each edge stored as {node, weight, index}.
5        vector<vector<array<int, 3>>> graph(n);
6        int edgeCount = edges.size();
7      
8        // Build the graph.
9        for (int i = 0; i < edgeCount; ++i) {
10            auto edge = edges[i];
11            int u = edge[0], v = edge[1], weight = edge[2];
12            graph[u].push_back({v, weight, i});
13            graph[v].push_back({u, weight, i});
14        }
15      
16        const int INF = 1 << 30; // Define infinity as a large number for initial distances.
17        vector<int> distance(n, INF);
18        distance[0] = 0; // Distance from the source node (0) to itself is 0.
19
20        using PairInt = pair<int, int>; // Pair to store {distance, node}.
21        priority_queue<PairInt, vector<PairInt>, greater<PairInt>> priorityQueue;
22        priorityQueue.push({0, 0}); // Start with the source node.
23
24        // Dijkstra's algorithm to find the shortest path from node 0.
25        while (!priorityQueue.empty()) {
26            auto [currentDistance, currentNode] = priorityQueue.top();
27            priorityQueue.pop();
28          
29            // If the current distance is larger than the stored distance, skip this node.
30            if (currentDistance > distance[currentNode]) {
31                continue;
32            }
33
34            // Explore neighbors.
35            for (auto [neighbor, weight, index] : graph[currentNode]) {
36                // Relaxation step.
37                if (distance[neighbor] > distance[currentNode] + weight) {
38                    distance[neighbor] = distance[currentNode] + weight;
39                    priorityQueue.push({distance[neighbor], neighbor});
40                }
41            }
42        }
43      
44        vector<bool> answer(edgeCount);
45      
46        // If the destination node (n-1) is unreachable, return a vector of false values.
47        if (distance[n - 1] == INF) {
48            return answer;
49        }
50      
51        // Backtrack from the destination node to find all edges in shortest paths.
52        queue<int> queue;
53        queue.push(n - 1);
54      
55        while (!queue.empty()) {
56            int currentNode = queue.front();
57            queue.pop();
58          
59            // Explore neighbors for backtracking.
60            for (auto [neighbor, weight, index] : graph[currentNode]) {
61                // Check if the edge is part of the shortest path.
62                if (distance[currentNode] == distance[neighbor] + weight) {
63                    answer[index] = true; // Mark this edge as part of the shortest path.
64                    queue.push(neighbor); // Continue to backtrack through this neighbor.
65                }
66            }
67        }
68      
69        return answer;
70    }
71};
72
1// Type definition for an edge element {node, weight, index}
2type EdgeElement = [number, number, number]; // [neighbor, weight, edgeIndex]
3
4// Function to find the answer based on shortest path analysis
5function findAnswer(n: number, edges: number[][]): boolean[] {
6    // Graph represented as an adjacency list with each edge stored as {node, weight, index}.
7    const graph: EdgeElement[][] = Array.from({ length: n }, () => []);
8    const edgeCount = edges.length;
9  
10    // Build the graph.
11    for (let i = 0; i < edgeCount; ++i) {
12        const edge = edges[i];
13        const u = edge[0], v = edge[1], weight = edge[2];
14        graph[u].push([v, weight, i]);
15        graph[v].push([u, weight, i]);
16    }
17  
18    const INF = 1 << 30; // Define infinity as a large number for initial distances.
19    const distance: number[] = Array(n).fill(INF);
20    distance[0] = 0; // Distance from the source node (0) to itself is 0.
21
22    type PairInt = [number, number]; // Pair to store {distance, node}.
23    const priorityQueue: PairInt[] = [];
24    priorityQueue.push([0, 0]); // Start with the source node.
25
26    // Comparator function for the priority queue
27    const comparator = ([distA]: PairInt, [distB]: PairInt) => distA - distB;
28
29    // Dijkstra's algorithm to find the shortest path from node 0.
30    while (priorityQueue.length > 0) {
31        // Sort the queue to behave as a priority queue
32        priorityQueue.sort(comparator);
33
34        const [currentDistance, currentNode] = priorityQueue.shift()!;
35
36        // If the current distance is larger than the stored distance, skip this node.
37        if (currentDistance > distance[currentNode]) {
38            continue;
39        }
40      
41        // Explore neighbors.
42        for (const [neighbor, weight, index] of graph[currentNode]) {
43            // Relaxation step.
44            if (distance[neighbor] > distance[currentNode] + weight) {
45                distance[neighbor] = distance[currentNode] + weight;
46                priorityQueue.push([distance[neighbor], neighbor]);
47            }
48        }
49    }
50  
51    const answer: boolean[] = new Array(edgeCount).fill(false);
52  
53    // If the destination node (n-1) is unreachable, return a vector of false values.
54    if (distance[n - 1] === INF) {
55        return answer;
56    }
57  
58    // Backtrack from the destination node to find all edges in shortest paths.
59    const queue: number[] = [];
60    queue.push(n - 1);
61  
62    while (queue.length > 0) {
63        const currentNode = queue.shift()!;
64      
65        // Explore neighbors for backtracking.
66        for (const [neighbor, weight, index] of graph[currentNode]) {
67            // Check if the edge is part of the shortest path.
68            if (distance[currentNode] === distance[neighbor] + weight) {
69                answer[index] = true; // Mark this edge as part of the shortest path.
70                queue.push(neighbor); // Continue to backtrack through this neighbor.
71            }
72        }
73    }
74  
75    return answer;
76}
77

Time and Space Complexity

The time complexity of the findAnswer function is O(m \times \log m), where m is the number of edges. This results primarily from using Dijkstra's algorithm, which employs a priority queue (min-heap) to determine the shortest path. In the worst case, each edge is processed in the priority queue, leading to the logarithmic factor.

The space complexity is O(n + m), where n is the number of nodes and m is the number of edges. This accounts for storing the graph as an adjacency list, maintaining distance values for each node, and using the priority and dequeue structures.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a good use case for backtracking?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More