Description

• Line 1 | Initializes single source with start vertex s – each vertex in G.V is first assigned the key value as ∞ (note that ∞ here is not a number, but a symbol to denote a number which is upper bound to all possible values of keys), and parent as NIL. In line 4, weight of start vertex specified, s is redefined to zero.
• Line 2-3 | Defines two sets: first one is named S, in which will store the list of edges in which we have already calculated the shortest path from start vertex ‘s’. Second one is Q – on which we would use min-priority queue, with the “d” attribute of each vertex as the key to order elements.
• Line 4 | Entering a loop, which will stop when the set Q is empty. This loop will stop in finite steps as out graphs are finite (i.e., has finite number of vertices and edges, and in each run of the loop, we will remove one edge from the queue Q and add it to the set S after finalising the shortest-path weight to that vertex from vertex ‘s’ .
  • Line 5-6 | We ‘extract’ the vertex in Q with lowest key, which we will call ‘u’ here and add it to the set S. On extraction, this particular vertex is removed from the set Q.
  • Line 7-8 | We will search the adjacency list of the extracted vertex ‘u’. If any vertex ‘v’ adjacent to ‘u’ has v.d > u.d + w(u,v), we change the value of v.d to u.d + w(u,v) and assign ‘u’ as the parent of v. If the condition is wrong, no changes are made.

Pages: Contents … << Previous 5 Next Page>>