Consider the following modification of Dijkstra’s algorithm: h ... initializatio
ID: 3600417 • Letter: C
Question
Consider the following modification of Dijkstra’s algorithm:
h ... initialization ... i
H := makequeue(V )
while H is not empty
v := deletemin(H)
for each e = (v, z) E
if dist(v) + w(v,z) < dist(z) then
dist(z) = dist(v) + w(v,z)
if z is in the queue H then decreasekey(H,z) else insert(H,z)
The modified algorithm correctly computes the distances in graphs with no negative cycles (negative
edges allowed). (Remember, original Dijkstra’s algorithm does not correctly compute distances if
negative edges are allowed.) Say something interesting about the running time of the modified
Dijkstra’s algorithm. Prove your statement.
Explanation / Answer
h ... initialization ... i
The number of vertices: V
The number of edges: E
We have to initialize each vertex and edge
To initialize one vertex or one edge it takes O(1) time
For N vertices and E edges time complexity will be O(N+E)
H := makequeue(V )
One insertion or Deletion into a queue takes O(1) time.
To construct a queue with V vertices takes O(V) time.
while H is not empty
Looping through H (H is a queue constructed earlier)
To loop through all the elements in H takes O(V), since there are V elements in the loop.
v := deletemin(H)
To delete mininimum first we need to find it.
To find the minum value we need to loop through H once again (because it is acceptable to find in the last iteration. I mean the last element can be the one with least value)
Hence time complexity is again O(V)
for each e = (v, z) E
Looping again over E takes O(E) time complexity.
Lets say there are 3 paths / edges from v to z stored in E and it is possible to have these edges stored at the start, middle or at the end in the List of Edges E.
if dist(v) + w(v,z) < dist(z) then
dist(z) = dist(v) + w(v,z)
if z is in the queue H then decreasekey(H,z) else insert(H,z)
If else only takes O(1) time complexity and insertion / deletion takes O(1) time complexity.
Hence the total complexity: O(1) + O(V) + O(V) * O(V) *O (E) * O(1)
O(V) * O(V) *O (E) * O(1): We are multiplying the complexities because they are part of the same while loop.
For each iteration of outer while loop, the complexity is O(V) *O (E) * O(1)
For V iterations of outer while loop, the complexity will be O(V) * O(V) *O (E) * O(1)