- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a number and a list of edges. These n different nodes labeled as 0 to N. These nodes are forming a network. Each edge is in the form (a, b, t) of an undirected graph, this is representing if we try to send message from a to b or b to a, it will take t time. When a node receives a message, it immediately floods the message on to a neighboring node. If all nodes are connected, we have to find how long it will take for every node to receive a message that starts at node 0.

So, if the input is like n = 3 edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]], then the output will be 9, as the 4th node (node number 3) receives the message from 0 -> 1 -> 2 -> 3 which takes 3 + 4 + 2 = 9 amount time.

To solve this, we will follow these steps −

Define a function build_graph() . This will take edges

- graph := an empty map
- for each (src, dest, t) set in edges, do
- insert (dest, t) into graph[src]
- insert (src, t) into graph[dest]

- return graph
- From the main method do the following −
- graph := build_graph(edges)
- visited := a new set
- heap := make a new heap with pair (0, 0)
- while heap is not empty, do
- (current_total_time, node) := top element of heap, and delete it from heap
- mark node as visited
- if number of visited nodes is same as (n + 1), then
- return current_total_time

- for each pair (nei, time) in graph[node], do
- if nei not visited, then
- insert pair (current_total_time + time, nei) into heap

- if nei not visited, then

Let us see the following implementation to get better understanding −

import heapq from collections import defaultdict class Solution: def solve(self, n, edges): graph = self.build_graph(edges) visited = set() heap = [(0, 0)] while heap: current_total_time, node = heapq.heappop(heap) visited.add(node) if len(visited) == (n + 1): return current_total_time for nei, time in graph[node]: if nei not in visited: heapq.heappush(heap, (current_total_time + time, nei)) def build_graph(self, edges): graph = defaultdict(set) for src, dest, t in edges: graph[src].add((dest, t)) graph[dest].add((src, t)) return graph ob = Solution() n = 3 edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]] print(ob.solve(n, edges))

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]

9

- Related Questions & Answers
- Program to find how many years it will take to reach t amount in Python
- Program to find minimum number of cells it will take to reach bottom right corner in Python
- How long does it take to learn Python?
- Program to find number of days it will take to burn all trees in python
- Why does it take so long to try criminals in India?
- Program to find minimum jumps to reach home in Python
- Program to find maximal network rank in Python
- Program to find minimum steps to reach target position by a chess knight in Python
- Program to Find Minimum Jumps Required to Reach a Value with Different Parity in Python
- Program to find number of given operations required to reach Target in Python
- Program to find number of minimum steps to reach last index in Python
- Program to find number of combinations of coins to reach target in Python
- Program to find out the shortest path to reach the goal in Python
- Program to find out the farthest building a parkour artist can reach in Python
- Program to find minimum number of hops required to reach end position in Python

Advertisements