634 views

Dijkstra’s algorithm is based on

2. Dynamic programming
3. Greedy approach

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

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.
by

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.

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

### 1 comment

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

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

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

1
2,084 views