Dijkstra's Algorithm
Dijkstra's Algorithm solves the single-source shortest path problem for a non-negative weighted graph. It's greedy in the way it finds the next node to expand, but it uses dynamic programming to compute the optimal distances. It works on both directed and undirected graphs.
Summary
Dijkstra's Algorithm solves the single-source shortest path problem for a non-negative weighted graph. It's greedy in the way it finds the next node to expand, but it uses dynamic programming to compute the optimal distances. It works on both directed and undirected graphs.
Things to Remember
- Dijkstra's Algorithm solves the single-source shortest path problem for a non-negative weighted graph.
- It's greedy in the way it finds the next node to expand, but it uses dynamic programming to compute the optimal distances.
- It works on both directed and undirected graphs.
MCQs
No MCQs found.
Subjective Questions
No subjective questions found.
Videos
No videos found.
Dijkstra's Algorithm
Dijkstra's Algorithm solves the single-source shortest path problem for a non-negative weighted graph. It's greedy in the way it finds the next node to expand, but it uses dynamic programming to compute the optimal distances. It finds the shortest path from an initial vertex to all the other vertices. It works on both directed and undirected graphs.
Example:
Consider the following weighted graph. What is the shortest path between vertices a and z?
Thus, the shortest distance is 12 and the correseponding path is (a,c,d,f,e,z).
References:
1.http://www.cs.laurentian.ca/jdompierre/html/MATH2056E_W2011/cours/s9.6_shortest_path_problems_BW.pdf
2.https://en.wikipedia.org/wiki/Dijkstra's_algorithm
3. Karumanchi, N. "Data Structures and Algorithms Made Easy"
4. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”
Lesson
Graphs
Subject
Computer Engineering
Grade
Engineering
Recent Notes
No recent notes.
Related Notes
No related notes.