Dijkstra Shortest Path Algorithm in Data Structure

Dijkstra shortest path algorithm in data structure is used to find the shortest path from one vertex to all other remaining vertices in the given weighted graph.
Dijkstra algorithm is also known as single shortest path algorithm because in this algorithm there is a single source vertex.

In this tutorial we will learn about the Dijkstra algorithm and how does it work ?

Dijkstra Algorithm based problems are also asked in GATE CSE and UGC Net exam. Problems based on Dijkstra algorithm is also explained in this tutorial.

Frequently asked questions

Some frequently asked questions from Dijkstra algorithm are given below

What is Dijkstra Algorithm ?
How does Dijkstra Algorithm work ?
What is difference between Dijkstra and Floyd Warshall algorithm ?

What is Dijkstra Shortest Path Algorithm

Various steps of Dijkstra Single Shortest Path Algorithm are as follow

Step 1- Marks the source vertex distance with 0 and rest with infinity.

Step 2 – Initially mark the source vertex as CURRENT and consider a set Visited Initially visited set is empty.

Step 3 – Find the adjacent of current vertex in the graph and change their distance from infinity to equal to the weight of path connecting from source to adjacent vertex.

Step 4 – Put the Current vertex in Visited set or mark current vertex as visited now.

Step 5 – Now the adjacent vertex which is at the minimum distance from source vertex select that vertex as Current.

Step 6 – Repeat step 3 to step 5 until all the vertices are visited.

Step 7- Stop algorithm when all the vertices are visited.

Dijkstra Algorithm Example

Dijkstra algorithm example is explained here in this section. Consider the questions given below

In the given graph source vertex as A and consider A as current vertex with distance 0 then we find the Adjacent of A which are B and D with distance 1 and 10 now we marked A as visited and since B is at the minimum distance so now we set B as current and repeat the same process for whole graph.