### 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

Section 24.3, Dijkstra’s Algorithm, Introduction to Algorithm by CLRSQ = V – Sto add to setS, we say that it uses a greedy strategy.

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

## One Comment Add yours