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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Edges in Shortest Paths

Number: 3386

Difficulty: Hard

Paid? No

Companies: WeRide

Problem Description

Given an undirected weighted graph with n nodes and m edges, determine which edges are part of at least one shortest path from node 0 to node n-1. Each edge is represented by [u, v, w] where w is the weight. If an edge lies on a shortest path, mark its corresponding position in the answer array as true; otherwise, mark it as false. Note that there may be multiple shortest paths between node 0 and node n-1.

Key Insights

  • Use Dijkstra's algorithm to compute the shortest distance from the start node (0) to all other nodes.
  • Since the graph is undirected, run another Dijkstra from the target node (n-1) to compute shortest distances from n-1.
  • An edge [u, v, w] is part of some shortest path if either:
    • distance(0 to u) + w + distance(v to n-1) equals the total shortest distance from 0 to n-1, or
    • distance(0 to v) + w + distance(u to n-1) equals the total shortest distance.
  • This two-pass Dijkstra method allows us to quickly check each edge’s potential to lie in a shortest path.

Space and Time Complexity

Time Complexity: O(m log n) for each Dijkstra run, total O(m log n) plus O(m) for the edge check.
Space Complexity: O(n + m) to store distances and the graph representation.

Solution

We first construct the graph using an adjacency list. Then we perform Dijkstra’s algorithm from node 0 to compute the shortest distances to all nodes (distStart). Similarly, we run Dijkstra’s algorithm from node n-1 on the same graph (since it is undirected) to get distances from n-1 (distEnd). Let totalShortest = distStart[n-1].
For each edge [u, v, w], we check if either
distStart[u] + w + distEnd[v] == totalShortest
or
distStart[v] + w + distEnd[u] == totalShortest.
If either condition holds, this edge is part of at least one shortest path.
We then return the boolean array answer accordingly.

Code Solutions

import heapq

def findEdgesInShortestPaths(n, edges):
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for idx, (u, v, w) in enumerate(edges):
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # Dijkstra function to compute shortest distances from a given start node
    def dijkstra(start):
        dist = [float('inf')] * n
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            cur_dist, node = heapq.heappop(heap)
            if cur_dist > dist[node]:
                continue
            for neighbor, weight in graph[node]:
                new_dist = cur_dist + weight
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor))
        return dist

    # Compute shortest distances from node 0 and from node n-1
    distStart = dijkstra(0)
    distEnd = dijkstra(n - 1)
    totalShortest = distStart[n - 1]
    
    result = []
    # Check for each edge if it can be part of a shortest path
    for u, v, w in edges:
        # Check two possibilities because the graph is undirected
        if distStart[u] + w + distEnd[v] == totalShortest or distStart[v] + w + distEnd[u] == totalShortest:
            result.append(True)
        else:
            result.append(False)
    return result

# Example usage:
# 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]]
# print(findEdgesInShortestPaths(n, edges))
← Back to All Questions