Minimum Distance to a Leaf Node in a Weighted Undirected Graph
Given an undirected tree having N nodes numbered from 0 to N – 1. Additionally, a 2D integer array, edges[][] of length N – 1, is provided, where edges[i]=[u, v, w] indicates an undirected edge between nodes u and v with a weight w.
The task is to return an answer array of length N, where answer[i] represents the minimum time required for i’th node to reach any leaf node.
Note: The total time taken to reach from one node to another is the sum of all the edge weight in the path.
Examples:
Input: N = 3, edges[][]={{0, 1, 5}, {1, 2, 3}}
Output: {0,3,0}
Explanation:
Nodes 0 and 2 are identified as magical nodes due to their single edge connection (degree is 1). Consequently, the minimum time required to reach a magical node from both 0 and 2 is 0.
Now, considering node 1, the minimum time to reach a magical node is determined as min(5, 3), resulting in 3.Input: N = 5, edges[][] = {{0, 1, 6}, {1, 4, 10}, {0, 2, 4}, {2, 3, 8}}
Output: {12,10,8,0,0}
Explanation:
In this scenario, nodes 3 and 4, with a degree of 1 (as connected with 1 edge), are designated as magical nodes.
For node 2, the minimum time required to reach node 3 is 8, and the time required to reach node 4 is 20.
Therefore, the answer for the 2nd node is 8. Similarly, for nodes 0 and 1, the respective answers are 12 and 10.
Approach: To solve the problem, follow the below idea:
The main idea is to use Dijkstra’s algorithm to efficiently find the minimum time to reach leaf node from each node in the tree. We start a multi-source Dijkstra’s algorithm where all the leaves are considered as source nodes. Now, running Dijkstra’s Algorithm will get us the minimum distance of all the nodes from any leaf node. Since, the graph is undirected the minimum distance from leaf nodes to a node is same as the minimum distance from that node to the leaf nodes.
Step-by-step algorithm:
- Create an adjacency list graph[][] to represent the tree structure, where each node is connected to its neighboring nodes with their respective travel times.
- Initialize a distance array distance[] to store the minimum time required to reach a leaf node from each node. Initialize all distances to infinity (LLONG_MAX).
- Create a priority queue pq to store nodes with their corresponding distances.
- Initially, add all leaf nodes to the priority queue with a distance of 0.
- Use Dijkstra’s algorithm to process nodes from the priority queue.
- For each node, update the distance to its neighboring nodes if a shorter path is found.
- Continue processing nodes until the priority queue is empty.
- Return the distance array, which contains the minimum time to reach a magical node from each node.
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find distance for each node vector< long long > disTree( int n, vector<vector< int > >& edges) { // Create a adjency matrix vector<vector<pair< long long , long long > > > graph(n); // Interate in edges for ( int i = 0; i < edges.size(); ++i) { long long x = edges[i][0]; long long y = edges[i][1]; long long w = edges[i][2]; graph[x].emplace_back(y, w); graph[y].emplace_back(x, w); } // Intialize a vector distance vector< long long > distance(n, LLONG_MAX); priority_queue<pair< long long , long long >, vector<pair< long long , long long > >, greater<pair< long long , long long > > > pq; // Nodes having degree 1 for ( int i = 0; i < n; ++i) { if (graph[i].size() == 1) { pq.push({ 0, i }); } } // Iterate in queue while (!pq.empty()) { auto temp = pq.top(); pq.pop(); long long dist = temp.first; long long node = temp.second; // If distance of node is already less if (distance[node] <= dist) { continue ; } // Otherwise assign the distance distance[node] = dist; // Iterate for nodes attach to node for ( const auto & e : graph[node]) { long long v = e.first; long long t = e.second; // If distance is less if (distance[v] > dist + t) { pq.push({ dist + t, v }); } } } // Return the vector return distance; } // Driver code int main() { int n = 3; vector<vector< int > > edges = { { 0, 1, 5 }, { 1, 2, 3 } }; // Function call vector< long long > ans = disTree(n, edges); // Print the ans for ( auto a : ans) { cout << a << " " ; } return 0; } |
Java
import java.util.*; public class Main { // Function to find distance for each node static List<Long> disTree( int n, List<List<Integer> > edges) { // Create an adjacency list List<List<Pair> > graph = new ArrayList<>(n); for ( int i = 0 ; i < n; ++i) { graph.add( new ArrayList<>()); } // Iterate in edges for ( int i = 0 ; i < edges.size(); ++i) { int x = edges.get(i).get( 0 ); int y = edges.get(i).get( 1 ); int w = edges.get(i).get( 2 ); graph.get(x).add( new Pair(y, w)); graph.get(y).add( new Pair(x, w)); } // Initialize a vector distance List<Long> distance = new ArrayList<>( Collections.nCopies(n, Long.MAX_VALUE)); PriorityQueue<Pair> pq = new PriorityQueue<>( Comparator.comparingLong(Pair::getFirst)); // Nodes having degree 1 for ( int i = 0 ; i < n; ++i) { if (graph.get(i).size() == 1 ) { pq.add( new Pair( 0 , i)); } } // Iterate in queue while (!pq.isEmpty()) { Pair temp = pq.poll(); long dist = temp.getFirst(); int node = temp.getSecond(); // If distance of node is already less if (distance.get(node) <= dist) { continue ; } // Otherwise assign the distance distance.set(node, dist); // Iterate for nodes attached to node for (Pair e : graph.get(node)) { int v = ( int )e.getFirst(); // Updated to // cast to int long t = e.getSecond(); // If distance is less if (distance.get(v) > dist + t) { pq.add( new Pair(dist + t, v)); } } } // Return the vector return distance; } // Driver code public static void main(String[] args) { int n = 3 ; List<List<Integer> > edges = List.of(List.of( 0 , 1 , 5 ), List.of( 1 , 2 , 3 )); // Function call List<Long> ans = disTree(n, edges); // Print the ans for ( long a : ans) { System.out.print(a + " " ); } } // Pair class to represent pair of integers static class Pair { private final long first; private final int second; public Pair( long first, int second) { this .first = first; this .second = second; } public long getFirst() { return first; } public int getSecond() { return second; } } } // This code is contributed by akshitaguprzj3 |
C#
using System; using System.Collections.Generic; class Program { // Function to find distance for each node static List< long > DisTree( int n, List<List< int >> edges) { // Create an adjacency list List<List<Tuple< long , long >>> graph = new List<List<Tuple< long , long >>>(n); // Initialize adjacency list for ( int i = 0; i < n; i++) { graph.Add( new List<Tuple< long , long >>()); } // Iterate over edges foreach (List< int > edge in edges) { long x = edge[0]; long y = edge[1]; long w = edge[2]; graph[( int )x].Add( new Tuple< long , long >(y, w)); graph[( int )y].Add( new Tuple< long , long >(x, w)); } // Initialize a vector distance List< long > distance = new List< long >(); for ( int i = 0; i < n; i++) { distance.Add( long .MaxValue); } // Priority queue for Dijkstra's algorithm PriorityQueue<Tuple< long , long >> pq = new PriorityQueue<Tuple< long , long >>( (x, y) => x.Item1.CompareTo(y.Item1) ); // Nodes having degree 1 for ( int i = 0; i < n; ++i) { if (graph[i].Count == 1) { pq.Enqueue( new Tuple< long , long >(0, i)); } } // Iterate in queue while (!pq.IsEmpty()) { Tuple< long , long > temp = pq.Dequeue(); long dist = temp.Item1; long node = temp.Item2; // If distance of node is already less, continue if (distance[( int )node] <= dist) { continue ; } // Assign the distance distance[( int )node] = dist; // Iterate for nodes attached to node foreach (Tuple< long , long > e in graph[( int )node]) { long v = e.Item1; long t = e.Item2; // If distance is less, enqueue if (distance[( int )v] > dist + t) { pq.Enqueue( new Tuple< long , long >(dist + t, v)); } } } // Return the vector return distance; } // Main method static void Main( string [] args) { int n = 3; List<List< int >> edges = new List<List< int >>() { new List< int >() { 0, 1, 5 }, new List< int >() { 1, 2, 3 } }; // Function call List< long > ans = DisTree(n, edges); // Print the ans foreach ( long a in ans) { Console.Write(a + " " ); } } } // Priority Queue implementation public class PriorityQueue<T> { private List<T> data; private Comparison<T> comparison; // Constructor public PriorityQueue(Comparison<T> comparison) { data = new List<T>(); this .comparison = comparison; } // Method to add an element to the priority queue public void Enqueue(T item) { data.Add(item); int ci = data.Count - 1; while (ci > 0) { int pi = (ci - 1) / 2; if (comparison(data[ci], data[pi]) >= 0) break ; T tmp = data[ci]; data[ci] = data[pi]; data[pi] = tmp; ci = pi; } } // Method to remove and return the element with the highest priority from the priority queue public T Dequeue() { int li = data.Count - 1; T frontItem = data[0]; data[0] = data[li]; data.RemoveAt(li); --li; int pi = 0; while ( true ) { int ci = pi * 2 + 1; if (ci > li) break ; int rc = ci + 1; if (rc <= li && comparison(data[rc], data[ci]) < 0) ci = rc; if (comparison(data[pi], data[ci]) <= 0) break ; T tmp = data[pi]; data[pi] = data[ci]; data[ci] = tmp; pi = ci; } return frontItem; } // Method to retrieve the element with the highest priority from the priority queue without removing it public T Peek() { T frontItem = data[0]; return frontItem; } // Property to get the count of elements in the priority queue public int Count { get { return data.Count; } } // Method to check if the priority queue is empty public bool IsEmpty() { return data.Count == 0; } } |
Javascript
class PriorityQueue { constructor(comparator) { this .heap = []; this .comparator = comparator; } add(value) { this .heap.push(value); this .bubbleUp(); } poll() { const top = this .heap[0]; const bottom = this .heap.pop(); if ( this .heap.length > 0) { this .heap[0] = bottom; this .bubbleDown(); } return top; } bubbleUp() { let index = this .heap.length - 1; while (index > 0) { const current = this .heap[index]; const parentIndex = Math.floor((index - 1) / 2); const parent = this .heap[parentIndex]; if ( this .comparator(current, parent) >= 0) break ; this .heap[index] = parent; this .heap[parentIndex] = current; index = parentIndex; } } bubbleDown() { let index = 0; const length = this .heap.length; const current = this .heap[0]; while ( true ) { let leftChildIndex = 2 * index + 1; let rightChildIndex = 2 * index + 2; let leftChild, rightChild; let swap = null ; if (leftChildIndex < length) { leftChild = this .heap[leftChildIndex]; if ( this .comparator(leftChild, current) < 0) { swap = leftChildIndex; } } if (rightChildIndex < length) { rightChild = this .heap[rightChildIndex]; if ((swap === null && this .comparator(rightChild, current) < 0) || (swap !== null && this .comparator(rightChild, leftChild) < 0)) { swap = rightChildIndex; } } if (swap === null ) break ; this .heap[index] = this .heap[swap]; this .heap[swap] = current; index = swap; } } peek() { return this .heap[0]; } size() { return this .heap.length; } } // Function to find distance for each node function disTree(n, edges) { // Create an adjacency list const graph = new Array(n).fill( null ).map(() => []); // Iterate over edges for (const edge of edges) { const [x, y, w] = edge; graph[x].push([y, w]); graph[y].push([x, w]); } // Initialize a distance array const distance = Array(n).fill(Number.MAX_SAFE_INTEGER); const pq = new PriorityQueue(([distA], [distB]) => distA - distB); // Nodes having degree 1 for (let i = 0; i < n; i++) { if (graph[i].length === 1) { pq.add([0, i]); } } // Iterate over the priority queue while (pq.size() > 0) { const [dist, node] = pq.poll(); // If distance of node is already less if (distance[node] <= dist) continue ; // Otherwise assign the distance distance[node] = dist; // Iterate for nodes attached to node for (const [v, t] of graph[node]) { // If distance is less if (distance[v] > dist + t) { pq.add([dist + t, v]); } } } // Return the distance array return distance; } // Driver code function main() { const n = 3; const edges = [[0, 1, 5], [1, 2, 3]]; // Function call const ans = disTree(n, edges); // Print the ans console.log( "Distances:" , ans.join( " " )); } // Invoke the main function main(); |
Python3
import heapq # Function to find distance for each node def disTree(n, edges): # Create an adjacency list graph = [[] for _ in range (n)] # Iterate over edges for edge in edges: x, y, w = edge graph[x].append((y, w)) graph[y].append((x, w)) # Initialize a list for distances distance = [ float ( 'inf' )] * n pq = [( 0 , i) for i in range (n) if len (graph[i]) = = 1 ] # Iterate in priority queue while pq: dist, node = heapq.heappop(pq) # If distance of node is already less if distance[node] < = dist: continue # Otherwise assign the distance distance[node] = dist # Iterate for nodes attached to node for v, t in graph[node]: # If distance is less if distance[v] > dist + t: heapq.heappush(pq, (dist + t, v)) # Return the list of distances return distance # Driver code def main(): n = 3 edges = [( 0 , 1 , 5 ), ( 1 , 2 , 3 )] # Function call ans = disTree(n, edges) # Print the answer for a in ans: print (a, end = " " ) # Call the main function if __name__ = = "__main__" : main() |
0 3 0
Time Complexity: O(N * log(N)), where N is the number of nodes in the graph.
Auxiliary Space: O(N)
Contact Us