{"id":6263,"date":"2025-09-13T12:37:35","date_gmt":"2025-09-13T07:07:35","guid":{"rendered":"https:\/\/study.madeeasy.in\/?p=6263"},"modified":"2025-09-26T11:39:19","modified_gmt":"2025-09-26T06:09:19","slug":"understanding-pseudocode","status":"publish","type":"post","link":"https:\/\/www.madeeasy.in\/study\/cs-it\/algorithms\/understanding-pseudocode","title":{"rendered":"Understanding Pseudocode"},"content":{"rendered":"<ol>\n<li style=\"text-align: justify;\">Line 1 performs the usual initialization of d and \u03c0 values and line 2 initializes the set S to the empty set.<\/li>\n<li style=\"text-align: justify;\">Line 3 initializes the min-heap Q to contain all the vertices in V.<\/li>\n<li style=\"text-align: justify;\">Each time through the lines 4 \u2013 6, a vertices u(whose d value is minimum) is extracted. Then lines 7 \u2013 8 relax edge (u, v) leaving u, thus updating the estimate u[v] and the predecessor \u03c0[v] if the shortest path to v can be improved by going through u.<\/li>\n<li style=\"text-align: justify;\">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 \u2013 8 iterates exactly [v] times.<\/li>\n<\/ol>\n<ul>\n<li style=\"text-align: justify;\">Because Dijkstra\u2019s algorithm always choose the \u201clightest\u201d or \u201cclosest\u201d vertex in V-S to insert into set S, we say that it uses a greedy strategy.<\/li>\n<li style=\"text-align: justify;\">Dijkstra\u2019s algorithm bears some similarity to both breadth-first search and Prim\u2019s 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.<\/li>\n<li style=\"text-align: justify;\">Dijkstra\u2019s algorithm is like prim\u2019s algorithm since both algorithms use a min-priority queue to find the \u201clightest\u201d vertex outside a given set (the set S in Dijkstra\u2019s algorithm and the tree being grown in prim\u2019s algorithm), add this vertex into the set, and adjust the weights of the remaining vertices outside the set accordingly<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Line 1 performs the usual initialization of d and \u03c0 values and line 2 initializes the set S to the<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1831,3],"tags":[1848,1847],"class_list":["post-6263","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-cs-it","tag-dijkstras-algorithm","tag-pseudocode"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6263","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/comments?post=6263"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6263\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6263"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}