2737. Find the Closest Marked Node

MediumGraphArrayShortest PathHeap (Priority Queue)

Problem Description

In this problem, we are given a directed weighted graph represented as a 2D array called edges, with each sub-array representing an edge in the format [start_node, end_node, weight]. The graph has n nodes that are 0-indexed, which means that nodes are numbered from 0 to n-1. We are also given a starting node s and an array of nodes called marked.

The objective is to determine the minimum distance from the starting node s to any node within the array marked. To clarify, the 'distance' here refers to the sum of the weights along the shortest path from s to the target node.

If there's no possible path from s to any of the nodes in marked, we return -1. The challenge lies in computing the shortest paths in an efficient manner, taking into consideration that the graph may contain edge cases like loops or multiple edges between two nodes.

Intuition

For the solution, we need an approach that allows us to find the shortest path from a source node to all other nodes in a graph. This points us towards the Dijkstra's algorithm, which is specifically designed for this purpose. However, we modify it slightly to use an adjacency matrix rather than a typical adjacency list, which is more efficient when dealing with dense graphs.

Here's the intuition behind the solution:

We initially set a graph matrix g with dimensions nxn, where g[u][v] will hold the minimum weight of all edges from node u to node v. If there are multiple edges between two nodes, we only keep the one with the least weight.
A distance array dist is created to keep track of the shortest distance from the start node s to every other node. Initially, all distances are set to infinity (inf), except for the distance from s to itself, which is 0.
We also have a boolean array vis to mark nodes as visited once their shortest distance is finalized.
The algorithm repeatedly finds the node with the smallest known distance that hasn't been visited yet. This node is marked as visited, and we examine all of its neighbors.
For each neighbor, we update its distance in the dist array if we find a shorter path through the current node. This step is repeated until distances to all nodes are finalized.
Finally, we find the minimum distance to all marked nodes and return that value, unless the minimum distance is infinity, which indicates that the nodes in marked are not reachable from s. In such a case, we return -1.

By using this modified version of Dijkstra's algorithm, we ensure that we check all possible paths in an efficient manner and determine the shortest path from s to a node in marked.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Solution Approach

The solution uses a modified Dijkstra's algorithm to find the shortest path from a single source to all nodes and then specifically to a subset of those nodes (marked nodes). Let's walk through the key steps of the implementation based on the provided python code:

Initialize the Graph Matrix: A graph matrix g is created to represent the weighted edges of the graph. It's initialized with inf (representing an absence of direct connection between nodes) and filled with actual weights where edges are present.

1g = [[inf] * n for _ in range(n)]
2for u, v, w in edges:
3    g[u][v] = min(g[u][v], w)

Set Initial Distances: dist array is set with inf values indicating unknown shortest paths. The distance from the source node s to itself is set to 0, as the shortest path from a node to itself is by definition no movement.
```
1dist = [inf] * n
2dist[s] = 0
```
Node Visitation Tracking: A boolean array vis keeps track of which nodes' shortest paths have been solidified. Initially, all nodes are set to False to indicate that no node's path has been finalized.
```
1vis = [False] * n
```

Algorithm Loop: The code executes a loop that iterates n times. Each iteration selects the non-visited node with the smallest known distance from the dist array.

1for _ in range(n):
2    t = -1
3    for j in range(n):
4        if not vis[j] and (t == -1 or dist[t] > dist[j]):
5            t = j

Update Shortest Paths: For the selected node, the algorithm iterates over all nodes and updates their shortest paths if a shorter path is found through the selected node.

1vis[t] = True
2for j in range(n):
3    dist[j] = min(dist[j], dist[t] + g[t][j])

Find Minimum Distances to Marked Nodes: After the loop ends, the distances to all marked nodes are found. It selects the smallest value from the dist array among the indices that correspond to the marked nodes.
```
1ans = min(dist[i] for i in marked)
```
Return the Result: The algorithm returns the shortest distance unless it is inf (in which case, it returns -1) because inf indicates no path was found from source s to any of the marked nodes.
```
1return -1 if ans >= inf else ans
```

The key data structures used here include a 2D list g for the graph representation, a list dist for tracking the shortest path distances, and vis, a list for tracking node visitation. The pattern used is iterative selection and relaxation of distances, characteristic of Dijkstra's algorithm.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Example Walkthrough

Let's consider a small graph with n = 4 nodes and s = 0 as the starting node. We have the edges and weights defined as follows:

edges = [[0, 1, 2], [0, 2, 5], [1, 2, 1], [2, 3, 1]]
marked = [2, 3]

The goal is to find the minimum distance from node 0 to any node in marked. Following the solution approach:

Initialize the Graph Matrix: We initialize a graph matrix g of size 4x4 with inf, except where there are actual connections:

1g = [
2    [inf,   2,   5, inf],
3    [inf, inf,   1, inf],
4    [inf, inf, inf,   1],
5    [inf, inf, inf, inf]
6]

We only keep the smallest weights between nodes.

Set Initial Distances: The dist array is initialized with inf, but we set dist[0] to 0 because that is our start node:
```
1dist = [0, inf, inf, inf]
```
Node Visitation Tracking: We track which nodes have been visited in an array vis, with all elements initially set to False:
```
1vis = [False, False, False, False]
```

Algorithm Loop: We loop through the nodes to find the non-visited node with the smallest distance each time. As we start with s = 0, it is the first to be selected and marked visited:

1vis = [True, False, False, False]  # Mark node 0 as visited

Update Shortest Paths: We update the shortest path to all the other nodes from node 0. After the first iteration, due to directly connected edges, dist array would be updated as follows:
```
1dist = [0, 2, 5, inf]
```
Continuing with the algorithm, node 1 would be chosen next and dist would be updated to:
```
1dist = [0, 2, 3, inf]
```
Then, node 2 would be chosen, and dist would be updated to:
```
1dist = [0, 2, 3, 4]
```
Find Minimum Distances to Marked Nodes: After processing all nodes, we look at the dist values of the marked nodes [2, 3], which are 3 and 4, respectively.
Return the Result: We select the minimum distance to a marked node, which is 3 for node 2, and since it's not inf, we return 3:
```
1return 3
```

In this small example, the minimum distance from node 0 to any node in marked is 3, which is the distance from node 0 to node 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumDistance(self, n: int, edges: List[List[int]], start: int, marked: List[int]) -> int:
5        # Initialize constants for infinite distance
6        INF = float('inf')
7      
8        # Construct the graph using an adjacency matrix with distances.
9        # Initially, all distances are set to infinity.
10        graph = [[INF] * n for _ in range(n)]
11      
12        # Update the graph with the given edges, ensuring to store the minimum weight
13        # if there are multiple edges between two nodes.
14        for u, v, weight in edges:
15            graph[u][v] = min(graph[u][v], weight)
16      
17        # Initialize distances from the start to all other nodes as infinity.
18        distances = [INF] * n
19        # Initialize all nodes as unvisited
20        visited = [False] * n
21        # The distance from the start node to itself is always 0
22        distances[start] = 0
23      
24        # Perform n iterations to find the shortest paths to all nodes
25        for _ in range(n):
26            closest_node = -1
27            # Find the unvisited node with the smallest distance
28            for j in range(n):
29                if not visited[j] and (closest_node == -1 or distances[closest_node] > distances[j]):
30                    closest_node = j
31          
32            # Mark the found node as visited
33            visited[closest_node] = True
34          
35            # Update the distance to each node in the graph
36            for j in range(n):
37                distances[j] = min(distances[j], distances[closest_node] + graph[closest_node][j])
38      
39        # Find the minimum distance to any of the marked nodes
40        min_distance_to_marked = min(distances[i] for i in marked)
41      
42        # If the minimum distance is infinity, no path exists; return -1.
43        # Otherwise, return the minimum distance found.
44        return -1 if min_distance_to_marked == INF else min_distance_to_marked
45

1import java.util.Arrays;
2import java.util.List;
3
4class Solution {
5    public int minimumDistance(int numNodes, List<List<Integer>> edges, int source, int[] markedNodes) {
6        final int INFINITY = 1 << 29; // Define an "infinite" distance for initialization purposes, larger than any possible path
7      
8        // Create and initialize the adjacency matrix with INFINITY, reflecting no direct paths yet
9        int[][] graph = new int[numNodes][numNodes]; 
10        for (int[] row : graph) {
11            Arrays.fill(row, INFINITY);
12        }
13      
14        // Fill the adjacency matrix with the minimum weights for each edge
15        for (List<Integer> edge : edges) {
16            int from = edge.get(0), to = edge.get(1), weight = edge.get(2);
17            graph[from][to] = Math.min(graph[from][to], weight);
18        }
19      
20        // Initialize distance array, setting the distance to all nodes to INFINITY, except the source
21        int[] distances = new int[numNodes]; 
22        Arrays.fill(distances, INFINITY);
23        distances[source] = 0;
24      
25        // Create a visited array to mark nodes as visited during the Dijkstra's algorithm
26        boolean[] visited = new boolean[numNodes];
27      
28        // Perform Dijkstra's algorithm to find shortest paths from the source to all nodes
29        for (int i = 0; i < numNodes; ++i) {
30            int closestNonVisitedNode = -1;
31            // Find the closest non-visited node
32            for (int j = 0; j < numNodes; ++j) {
33                if (!visited[j] && (closestNonVisitedNode == -1 || distances[closestNonVisitedNode] > distances[j])) {
34                    closestNonVisitedNode = j;
35                }
36            }
37          
38            // Mark the found node as visited
39            visited[closestNonVisitedNode] = true;
40          
41            // Update the distance to each node from the found node
42            for (int j = 0; j < numNodes; ++j) {
43                distances[j] = Math.min(distances[j], distances[closestNonVisitedNode] + graph[closestNonVisitedNode][j]);
44            }
45        }
46      
47        // Determine the minimum distance to all marked nodes
48        int minimumDistance = INFINITY;
49        for (int markedNode : markedNodes) {
50            minimumDistance = Math.min(minimumDistance, distances[markedNode]);
51        }
52      
53        // If the minimumDistance is INFINITY, then return -1 indicating no path found; otherwise, return the minimumDistance
54        return minimumDistance >= INFINITY ? -1 : minimumDistance;
55    }
56}
57

1#include<vector>
2#include<algorithm>
3#include<climits>
4
5using namespace std;
6
7class Solution {
8public:
9    int minimumDistance(int numNodes, vector<vector<int>>& edges, int startNode, vector<int>& markedNodes) {
10        const int INF = INT_MAX; // A constant representing the value for infinity.
11        vector<vector<int>> graph(numNodes, vector<int>(numNodes, INF)); // Adjacency matrix initialized with INF distances.
12        vector<int> distances(numNodes, INF); // Vector to hold the shortest distances from the start node; initialized with INF.
13        distances[startNode] = 0; // Distance from the start node to itself is 0.
14        vector<bool> visited(numNodes, false); // Keep track of visited nodes; initialized to false.
15
16        // Updating the graph with the minimum weights from edges input.
17        for (auto& edge : edges) {
18            int source = edge[0], destination = edge[1], weight = edge[2];
19            graph[source][destination] = min(graph[source][destination], weight); // Ensure the smallest edge weight is used.
20        }
21
22        // Dijkstra's Algorithm to calculate the shortest path from the start node to all others.
23        for (int i = 0; i < numNodes; ++i) {
24            int nearest = -1;
25
26            // Find the unvisited node with the smallest distance.
27            for (int j = 0; j < numNodes; ++j) {
28                if (!visited[j] && (nearest == -1 || distances[nearest] > distances[j])) {
29                    nearest = j;
30                }
31            }
32
33            visited[nearest] = true; // Mark the nearest node as visited.
34
35            // Update distances for all adjacent nodes.
36            for (int j = 0; j < numNodes; ++j) {
37                if(distances[nearest] != INF && graph[nearest][j] != INF) { // Only proceed if paths exist and are finite.
38                    distances[j] = min(distances[j], distances[nearest] + graph[nearest][j]);
39                }
40            }
41        }
42
43        // Initialize the answer as infinity.
44        int answer = INF;
45        // Find the minimum distance to each of the marked nodes.
46        for (int markedNode : markedNodes) {
47            answer = min(answer, distances[markedNode]);
48        }
49
50        // If answer is still INF, no path exists to any of the marked nodes; return -1.
51        return answer == INF ? -1 : answer;
52    }
53};
54

1function minimumDistance(nodeCount: number, edgeList: number[][], startNode: number, targetNodes: number[]): number {
2    const infinity = Number.MAX_SAFE_INTEGER; // A representation of 'infinity' using the max safe integer in JavaScript
3    // Initialize adjacency matrix with 'infinity' representing no direct path between nodes
4    let graph: number[][] = Array.from(Array(nodeCount), () => Array(nodeCount).fill(infinity));
5    let distances: number[] = Array(nodeCount).fill(infinity); // Distance from startNode to every other node
6    let visited: boolean[] = Array(nodeCount).fill(false); // Tracks if a node has been visited
7
8    // Construct the graph with the minimum weight for each edge, in case of multiple edges between the same nodes
9    for (let [from, to, weight] of edgeList) {
10        graph[from][to] = Math.min(graph[from][to], weight);
11    }
12
13    // Distance from startNode to itself is zero
14    distances[startNode] = 0;
15
16    // Implement Dijkstra's algorithm to find the shortest paths from startNode to all other nodes
17    for (let i = 0; i < nodeCount; ++i) {
18        let closestNode = -1;
19        // Find the unvisited node with the smallest distance
20        for (let j = 0; j < nodeCount; ++j) {
21            if (!visited[j] && (closestNode === -1 || distances[closestNode] > distances[j])) {
22                closestNode = j;
23            }
24        }
25        // Mark the chosen node as visited
26        visited[closestNode] = true;
27
28        // Update distances to adjacent nodes if they provide a shorter path
29        for (let j = 0; j < nodeCount; ++j) {
30            distances[j] = Math.min(distances[j], distances[closestNode] + graph[closestNode][j]);
31        }
32    }
33
34    // Find the minimum distance to any of the target nodes specified in the "targetNodes" array
35    let minimumDistance = infinity;
36    for (let targetNode of targetNodes) {
37        minimumDistance = Math.min(minimumDistance, distances[targetNode]);
38    }
39
40    // If the minimum distance is infinity, no path exists to any target node, so return -1; Otherwise, return the minimum distance
41    return minimumDistance >= infinity ? -1 : minimumDistance;
42}
43

Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Time and Space Complexity

Time Complexity

The given code implements a modified version of the Dijkstra's algorithm for finding the shortest path from a single source to all other vertices in a graph.

Initializing the graph 'g', 'dist', and 'vis' lists takes O(n^2), O(n), and O(n) time complexities respectively, where 'n' is the number of nodes in the graph.
The outer for loop runs for 'n' iterations, and within this loop:
- Selecting the node 't' with the minimum distance 'dist[t]' that is not visited yet, requires iterating over all 'n' nodes. So it takes O(n) time per iteration, resulting in O(n^2) for all 'n' iterations.
- The nested inner for loop also iterates over 'n' nodes to update the distance 'dist[j]'. Therefore, it takes O(n) time per outer loop iteration, resulting in O(n^2) for all 'n' iterations of the outer loop.

Combining these together, the time complexity of the code is dominated by the two nested 'n' iterations, resulting in a total time complexity of O(n^2 + n^2), which simplifies to O(n^2).

Space Complexity

The space complexity for the graph representation 'g' is O(n^2) since it stores the weights for each pair of vertices.
'dist' and 'vis' arrays each take O(n) space.

Thus, the overall space complexity of the code is the sum of the space taken by 'g', 'dist', and 'vis', resulting in O(n^2 + n + n), which simplifies to O(n^2).

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2737. Find the Closest Marked Node

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings