Introduction

In this blog post, we will explore how to solve the LeetCode problem "3123" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: 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]] Output: [true,true,true,false,true,true,true,false] Explanation: The following are all the shortest paths between nodes 0 and 5: The path 0 -> 1 -> 5: The sum of weights is 4 + 1 = 5. The path 0 -> 2 -> 3 -> 5: The sum of weights is 1 + 1 + 3 = 5. The path 0 -> 2 -> 3 -> 1 -> 5: The sum of weights is 1 + 1 + 2 + 1 = 5. Example 2: Input: n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]] Output: [true,false,false,true] Explanation: There is one shortest path between nodes 0 and 3, which is the path 0 -> 2 -> 3 with the sum of weights 1 + 2 = 3. Constraints: 2 <= n <= 5 104 m == edges.length 1 <= m <= min(5 104, n * (n - 1) / 2) 0 <= ai, bi < n ai != bi 1 <= wi <= 105 There are no repeated edges.

Explanation

Here's the solution approach, runtime analysis, and Python code to solve this problem:

• Find shortest path length: Use Dijkstra's algorithm to compute the shortest distance from the source node (0) to the destination node (n-1).

• Identify edges on shortest paths: Again, use Dijkstra's, but this time, when exploring neighbors, check if the edge (u, v) is part of any shortest path. An edge (u, v) with weight w is part of a shortest path if dist[u] + w + dist[v, n-1] == dist[0, n-1]. We calculate the dist[v, n-1] using a reversed graph and Dijkstra from n-1 to all nodes.

• Build boolean array: Build the answer array by checking if each edge satisfies the shortest path condition identified in the previous step.

• Runtime & Space Complexity:

  • Runtime: O(m log n), where n is the number of nodes and m is the number of edges. This is primarily due to Dijkstra's algorithm being used twice.
  • Space: O(n + m) to store the graph, distances, and the boolean answer array.

Code

    import heapq

def find_edges_in_shortest_paths(n: int, edges: list[list[int]]) -> list[bool]:
    """
    Finds the edges that are part of at least one shortest path from node 0 to node n-1.
    """

    def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> list[int]:
        """
        Computes the shortest distances from a starting node to all other nodes in the graph.
        """
        dist = [float('inf')] * n
        dist[start] = 0
        pq = [(0, start)]  # (distance, node)

        while pq:
            d, u = heapq.heappop(pq)

            if d > dist[u]:
                continue

            if u not in graph:
                continue

            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heapq.heappush(pq, (dist[v], v))

        return dist

    # Build the adjacency list representation of the graph
    graph = {i: [] for i in range(n)}
    reversed_graph = {i: [] for i in range(n)}
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
        reversed_graph[v].append((u, w))
        reversed_graph[u].append((v, w))

    #Calculate shortest path from 0 to n-1
    dist_from_start = dijkstra(graph, 0)
    shortest_path_len = dist_from_start[n-1]

    #Calculate shortest path from n-1 to all nodes
    dist_from_end = dijkstra(reversed_graph, n-1)

    if shortest_path_len == float('inf'):
        return [False] * len(edges)

    answer = [False] * len(edges)
    for i, (u, v, w) in enumerate(edges):
        if dist_from_start[u] + w + dist_from_end[v] == shortest_path_len or \
           dist_from_start[v] + w + dist_from_end[u] == shortest_path_len:
            answer[i] = True

    return answer