A Bit About Dijkstra’s

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.

Why is Dijkstra’s Algorithm Called a Greedy Algorithm?

Quoting CLRS:

Because Dijkstra’s algorithm always chooses the “lightest” or “closest” vertex in Q = V – S to add to set S, we say that it uses a greedy strategy.

Section 24.3, Dijkstra’s Algorithm, Introduction to Algorithm by CLRS

Pages: Contents<< Previous 5 Next Page>>

One Comment Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.