Understanding Pseudocode
- Line 1 performs the usual initialization of d and π values and line 2 initializes the set S to the empty set.
- Line 3 initializes the min-heap Q to contain all the vertices in V.
- Each time through the lines 4 – 6, a vertices u(whose d value is minimum) is extracted. Then lines 7 – 8 relax edge (u, v) leaving u, thus updating the estimate u[v] and the predecessor π[v] if the shortest path to v can be improved by going through u.
- Observe that vertices are never inserted into Q after line 3 and that each vertex is extracted from Q and added to S exactly once, so that the while loop of lines 4 – 8 iterates exactly [v] times.
- Because Dijkstra’s algorithm always choose the “lightest” or “closest” vertex in V-S to insert into set S, we say that it uses a greedy strategy.
- Dijkstra’s algorithm bears some similarity to both breadth-first search and Prim’s algorithm for computing minimum spanning trees. It is like breadth-first search in that set S corresponds to the set of black vertices in a breadth-first search; just as vertices in S have their final shortest-path weights, so do black vertices in a breadth-first search have their correct breadth-first distances.
- Dijkstra’s algorithm is like prim’s algorithm since both algorithms use a min-priority queue to find the “lightest” vertex outside a given set (the set S in Dijkstra’s algorithm and the tree being grown in prim’s algorithm), add this vertex into the set, and adjust the weights of the remaining vertices outside the set accordingly
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
