2. A greedy algorithm is one in which a locally optimal choice (i.e. best possib

Question

2. A greedy algorithm is one in which a locally optimal choice (i.e. best possible choice using only immediate context) is made at each step in the algorithm, with the hope that this will yield the best possible overall solution for the entire problem. Dijkstra's Algorithm is considered greedy by this definition. What locally-optimal choice does Dijkstra's make? In other words, what "choice does Dijkstra's algorithm make based on maximum or minimum values seen so far, that turns out to produce an overall solution to the problem when combined with many other such choices over the course of the algorithm? (Hint: one of the lecture slides is of great value for answering this question.)

Explanation / Answer

At each step in Dijkstra's algorithm it picks the next vertex, the vertex that has the shortest know path from the current vertex up until we reach the final vertex(end point). This choice of choosing the vertex with the shortest distance, upto which the path is know when combined over the course of the Algorithm will lead to shortest path between the starting and the endpoints.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.