in Algorithms recategorized
559 views
0 votes
0 votes

Dijkstra’s algorithm is based on

  1. Divide and conquer paradigm
  2. Dynamic programming
  3. Greedy approach
  4. Backtracking paradigm
in Algorithms recategorized
559 views

4 Comments

I felt it should be dynamic, but some places are writing its greedy and some places are writing its dynamic. am confused  now
0
0
It's greedy cause at every point we greedily choose the smallest distance from the source
0
0
and it can be dynamic cz each tym it is updated?isnt it?
0
0
greedy approach
0
0

4 Answers

1 vote
1 vote
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.
edited by

2 Comments

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.
1
1
0 votes
0 votes

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?

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

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

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

Answer:

Related questions