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 the Closest Marked Node

Number: 2880

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a directed weighted graph with n nodes (0-indexed) represented by the array edges, where each edge is given as [u, v, w] (an edge from u to v with weight w), and a source node s along with a list of marked nodes, the goal is to determine the minimum distance from s to any of the marked nodes. If no marked node is reachable from the source s, return -1.

Key Insights

  • The problem requires computing the shortest path from a source node to a set of target nodes.
  • Dijkstra's algorithm is a natural fit since the graph has non-negative edge weights.
  • Use a min-heap (or priority queue) to efficiently extract the node with the smallest distance.
  • As soon as a marked node is reached, its distance can be considered as a candidate and the minimum among these is desired.
  • There is a possibility that some marked nodes may be unreachable, so if none are reachable, return -1.

Space and Time Complexity

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

Solution

We employ Dijkstra's algorithm to compute the shortest paths from node s to all other nodes in the graph. We begin by constructing the adjacency list from the input edges. A min-heap (or priority queue) is used to repeatedly extract the next node with the minimum known distance. Once a marked node is extracted (or its distance is finalized), its distance can be considered as a candidate. The algorithm iterates until all possible nodes are visited, and finally returns the minimum distance among all encountered marked nodes. If no path to any marked node exists, -1 is returned.

Code Solutions

import heapq

def findClosestMarkedNode(n, edges, s, marked):
    # Create an adjacency list for the graph
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    
    # Convert marked list to a set for O(1) look-ups
    marked_set = set(marked)
    
    # Distance array, initialize with infinity
    distances = [float('inf')] * n
    distances[s] = 0
    
    # Min-heap for Dijkstra's algorithm, stores (distance, node)
    heap = [(0, s)]
    
    # Result variable to track the smallest distance to a marked node
    result = float('inf')
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        
        # Skip processing if we found a better route already
        if current_dist > distances[u]:
            continue
        
        # If the current node is marked, update the result
        if u in marked_set:
            result = min(result, current_dist)
        
        # Explore all neighbors of the current node
        for v, weight in graph[u]:
            if current_dist + weight < distances[v]:
                distances[v] = current_dist + weight
                heapq.heappush(heap, (distances[v], v))
    
    return result if result != float('inf') else -1

# Example usage:
print(findClosestMarkedNode(4, [[0,1,1],[1,2,3],[2,3,2],[0,3,4]], 0, [2,3]))
← Back to All Questions