Efficient Solution for Network Delay Time Problem Using Dijkstra's Algorithm in C++

[poshithNandyala]

This pull request addresses issue #105 and provides an efficient solution to the Network Delay Time problem, implemented in C++. The problem involves determining the minimum time required for all nodes in a directed, weighted network graph to receive a signal sent from a specified starting node, k. If any nodes are unreachable, the solution returns -1 to indicate this.

The approach uses Dijkstra's Algorithm for shortest-path computation, ensuring an optimal time complexity for large graphs by utilizing a min-heap (priority queue) to manage nodes in the order of their current shortest distance from the source node. This solution:

• Constructs an adjacency list for representing the graph's edges and weights.
• Initializes a distance vector with "infinity" for all nodes except the starting node, which is set to zero.
• Iteratively processes each node, updating the shortest path to its neighboring nodes through a relaxation process.
• Utilizes a min-heap to efficiently retrieve and expand the node with the current minimum distance, a crucial optimization for Dijkstra’s Algorithm.

Summary of Changes

• Implements the graph as an adjacency list.
• Applies Dijkstra’s Algorithm to compute the shortest path from the source node to all other nodes.
• Includes necessary edge cases, such as handling unreachable nodes.

Additional Information

• Contributor: Poshith
• Contribution as part of: Hacktoberfest

This solution provides clarity and efficiency in handling the Network Delay Time problem, offering robust performance for the upper bounds of constraints.

[github-actions[bot]]

Thank you for submitting your pull request! 🙌 We'll review it as soon as possible. In the meantime, please ensure that you star the repository and follow me in github,otherwise PR will not merged. If there are any specific instructions or feedback regarding your PR, we'll provide them here. Thanks again for your contribution! 😊

[abhisek247767]

can you write the algo in same cpp file with explanation which you write in txt file.

[poshithNandyala]

I have added in-code explanations for Dijkstra's algorithm within the same CPP file. Please review the changes.