Horje
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()

Output

0 3 0

Time Complexity: O(N * log(N)), where N is the number of nodes in the graph.
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Minimize the maximum subarray sum with 1s and -2s Minimize the maximum subarray sum with 1s and -2s
Does a Data Scientist/Machine Learning Engineer require in depth knowledge of Data Structures and Algorithms? Does a Data Scientist/Machine Learning Engineer require in depth knowledge of Data Structures and Algorithms?
Find longest substring of S1 that matches in S2 with a given cost Find longest substring of S1 that matches in S2 with a given cost
Find the winner by incrementing co-ordinates till Euclidean distance &lt;= D Find the winner by incrementing co-ordinates till Euclidean distance &lt;= D
Modify shortest distance between source and destination to K Modify shortest distance between source and destination to K

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje