We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Edges in Shortest Paths

Difficulty: Hard

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] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi. 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. Return the array answer. Note that the graph may not be connected.

Key Insights

  • The problem requires finding edges that are part of any shortest path from node 0 to node n-1.
  • Dijkstra's algorithm can be used to find the shortest path distances from the source node (0) to all other nodes.
  • A reverse traversal of the graph can help determine which edges contribute to the shortest path to the destination node (n-1).
  • The solution must handle the case of multiple shortest paths.

Space and Time Complexity

Time Complexity: O(m log n), where m is the number of edges and n is the number of nodes, due to the priority queue used in Dijkstra's algorithm. Space Complexity: O(n + m) for storing the graph and other auxiliary data structures.

Solution

To solve the problem, we will use Dijkstra's algorithm to compute the shortest distances from the source node (0) to all other nodes. After obtaining the shortest distances, we will reverse the graph and check for each edge if it can be part of a shortest path to the destination node (n-1). We will maintain boolean flags for each edge to indicate if they are part of any shortest path.

Step-by-step Approach:

  1. Build the graph representation using an adjacency list.
  2. Use Dijkstra's algorithm to find the shortest distance from node 0 to all other nodes.
  3. For the destination node (n-1), retrieve the shortest path distance.
  4. Reverse the graph edges and perform a search (BFS or DFS) starting from node n-1 to determine which edges can reach node 0 while maintaining the shortest path distance.
  5. Mark the edges accordingly in the answer array.

Code Solutions

import heapq
from collections import defaultdict

def findEdgesInShortestPaths(n, edges):
    # Step 1: Build the graph
    graph = defaultdict(list)
    for i, (u, v, w) in enumerate(edges):
        graph[u].append((v, w, i))
        graph[v].append((u, w, i))
    
    # Step 2: Dijkstra's algorithm to find shortest path from node 0
    def dijkstra(source):
        dist = [float('inf')] * n
        dist[source] = 0
        min_heap = [(0, source)]
        
        while min_heap:
            curr_dist, node = heapq.heappop(min_heap)
            if curr_dist > dist[node]:
                continue
            for neighbor, weight, _ in graph[node]:
                if curr_dist + weight < dist[neighbor]:
                    dist[neighbor] = curr_dist + weight
                    heapq.heappush(min_heap, (dist[neighbor], neighbor))
        
        return dist
    
    shortest_distances = dijkstra(0)
    target_distance = shortest_distances[n - 1]
    
    # Step 3: Check which edges are part of the shortest paths
    answer = [False] * len(edges)
    
    # Step 4: Reverse graph for backward checking
    reverse_graph = defaultdict(list)
    for i, (u, v, w) in enumerate(edges):
        reverse_graph[v].append((u, w, i))
        reverse_graph[u].append((v, w, i))
    
    # Step 5: BFS/DFS from node n-1 to find valid edges
    def dfs(node):
        for neighbor, weight, edge_index in reverse_graph[node]:
            if shortest_distances[node] == shortest_distances[neighbor] + weight:
                answer[edge_index] = True
                dfs(neighbor)
    
    dfs(n - 1)
    
    return answer
← Back to All Questions