Data Structures | Python - Python Program For Dijkstra's Algorithm | Graph Data Structure

In this video, we explore how to implement Dijkstra's algorithm to find the shortest distance from a given node to all other nodes in a weighted graph using Python. **Dijkstra's algorithm** is a famous algorithm used in computer science for solving the "single-source shortest path" problem, which helps in finding the shortest paths between nodes in a graph. It is particularly useful when the graph has non-negative weights (edge costs) and can be represented using an adjacency list. The algorithm works by continuously selecting the node with the smallest tentative distance, visiting its neighbors, and updating their distances based on the smallest known path. This process repeats until all nodes are visited and the shortest distance for each node is finalized. The program begins by representing the graph using a dictionary where the keys are nodes and the values are lists containing tuples of adjacent nodes and the corresponding edge weights. A dictionary is then created to store the minimum distance from the source node to all other nodes. Initially, all distances are set to infinity, except for the source node, which is set to 0. A priority queue (using the `heapq` library) is used to keep track of the next node with the smallest tentative distance. This queue helps in efficiently selecting the node with the shortest distance at each step. For each node, the algorithm checks its neighbors and relaxes the edge, meaning it updates the distance to a neighboring node if a shorter path is found through the current node. Additionally, the program handles edge cases, such as when the starting node is not in the graph or if a node has already been visited with a shorter distance. After completing the process, the program outputs the shortest distance for every node from the chosen starting node, providing a comprehensive view of the shortest paths in the graph.