Dijkstra Algorithm Python

Introduction to Dijkstra’s Algorithm Python

Dijkstra is a well-known algorithm for finding the shortest path between any 2 nodes in the graph. This Dijkstra algorithm is developed by a Dutch programmer Edsger W. Dijkstra. This algorithm is somehow used for finding mutual friends the social media platforms routing the packets of data over the internet and many more. Now let's have a dive and find out what's the actual algorithm behind this.

Basic Algorithm

1. First create a list named visited vertices which keeps the account of vertices that are included in the shortest path that is nothing but the vertices whose minimum distance is calculated from the source and are finalized. At starting this list is empty.
2. Initially assign the distance value of the vertices as infinite except that source vertex, assign the source vertex distance value as 0 so that it can be picked up first.
3. While visited vertices doesn't include all the vertices:
   • Find out the vertex u among the neighboring vertices which are not there in the visited vertices and should have a minimum value among all of them.
   • Add that u vertex in the visited vertices list.
   • Now update the distance for each neighboring vertex(v) of that visited vertex, by calculating if the sum of the distance of u from the source and weight of an edge between u and v is less than the distance value of v(neighboring vertex).

Now let's move to the implementation part of this algorithm.

Implementation of Dijkstra Algorithm Python

Naive Method

Let's implement Dijkstra's naive method. The runtime of this Dijkstra Algorithm Python is $O(N^2)$.

Output

Using a Priority Queue

Here is the complete implementation of Dijkstra Algorithm Python with a priority queue. The runtime of this Dijkstra Algorithm Python is $O(N*logN)$.

Output

Dijkstra Algorithm Python Complexity

Naive Method

Time Complexity: The time complexity of Dijkstra Algorithm Python is $O(V^2)$ as there are 2 nested 'for' loops running for 'V' time i.e number of vertices.

Space Complexity The space complexity of Dijkstra Algorithm Python is $O(V)$.

Priority queue method

Time Complexity Then the time complexity of Dijkstra's Algorithm Python is $O(Elog(V))$, and here V is the number of vertices and E is the number of edges in the given graph.

Space Complexity The space complexity of Dijkstra Algorithm Python is $O(V)$.

Example of Dijkstra’s Algorithm Python

Now let's take an example to understand this concept more clearly.

So suppose there is a graph given below which is represented in the form of an adjacency list.

Now the adjacency list representation of the above graph is given below.

Now we have to find out the shortest path to each node from node "1".

So after implementing any of the 2 methods of Dijkstra's algorithm in this given example, we can find out the list which contains the shortest path to each node from node 1.

The shortest distance to each node from node 1 is listed below:

[4, 0, 9, 10, 11]

Applications of Dijkstra’s Algorithm Python

There are lots of real-life applications of Dijkstra's algorithm, some of which are given below:

1. Social Media Applications: These social media applications suggest some mutual friends which are friends of your friend, so this thing doesn't happen with a coincidence it is working on Dijkstra's algorithm.

2. Google Maps: Whenever we try to find out the path between 2 locations in Google Maps, then it shows us the most optimal or we can say the shortest path possible between those 2 locations, which is working on Dijkstra's algorithm.

3. IP routing: Dijkstra's algorithm is used here to find out the shortest distance between the source and destination. This helps the router to find out the minimum cost path from the source router to any other router.

4. Robots and Drones: Robots and drones come in 2 variants, one is manual and another one is automated the automated ones are used to deliver any kind of parcel from one location to another, so here also Dijkstra's algorithm is used to find out the shortest distance between the starting point and destination point.

There are many more real-life applications of this Dijkstra algorithm.

Similar Python Programs

1. Graph in Data Structure
2. Types of Graph in Data Structure
3. Graph Traversal in Data Structure
4. Depth First Search (DFS) Algorithm