Data Structures | Python - Python Program For Dijkstra Algorithm To Find Shortest Path | Graph Data Structure

In this tutorial, the focus is on finding the shortest distance and shortest path between nodes in a graph using Dijkstra's algorithm. To begin, two key variables are introduced: one for the source node and another for the target node. These variables are necessary as the source node is used to calculate the shortest distance, while both the source and target nodes are needed to determine the shortest path. Before invoking the function to calculate the shortest distance and the shortest path, the program first checks if both nodes exist in the graph. If either of the nodes is missing, a message is printed. If both nodes are valid, the program proceeds with the function calls to compute the shortest distance and shortest path. The algorithm starts by calling a function (`dijkstra`) that computes the shortest distance using the graph and source node. For the shortest path, a separate function (`shortest_path`) is introduced, which builds the path by keeping track of parent nodes. The parent node for each node is stored in a dictionary, which is updated as the algorithm processes each node. This allows the program to trace the path once the target node is reached. The program uses a dictionary comprehension to store the parent node of each node, initially setting them to `None`. As the algorithm progresses, the parent node is updated for each node visited. The distance and parent dictionaries are then returned. With these dictionaries, the program constructs the shortest path by tracing back from the target node to the source node. Finally, the program is designed to handle both the shortest distance and shortest path for individual nodes or from a node to all other nodes. It loops through all the nodes in the graph, printing the shortest distance and the shortest path for each.