UGC NET CSE | January 2017 | Part 3 | Question: 35

Question

Dijkstra’s algorithm is based on

• A. Divide and conquer paradigm
• B. Dynamic programming
• C. Greedy approach
• D. Backtracking paradigm

Comments

I felt it should be dynamic, but some places are writing its greedy and some places are writing its dynamic. am confused  now

---

It's greedy cause at every point we greedily choose the smallest distance from the source

---

and it can be dynamic cz each tym it is updated?isnt it?

---

greedy approach

Answer 1

Dijkstra always chooses the closest vertex in V-S to add to set S where V= vertex set and S =set of vertices whose final shortest path weights from the source  have been obtained.

So Dijkstra's algorithm is a greedy algorithm.Hence answer is option 3.

Comments

then what about this.. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic_programming_perspective

---

Dijkstra always chooses the closest vertex in V-S to add to set S where V= vertex set and S =set of vertices whose final shortest path weights frm the source  have been obtained.

So it is a greedy strategy.

Answer 2

Option C) Greedy Approach. On every iteration the vertex with the least distance after edge relaxation (best choice at that point of time i.e Greedy approach) is added to the list of mapped vertices

Comments

  it can be dynamic cz each tym it is updated?isnt it?

what about this.. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic_programming_perspective

Answer 3

dijkstra comes under single source shortest path algo. which is application of greedy method

Answer 4

Dijkstra’s algorithm is based on Greedy approach.so option c is right.