[7.5] Dijkstra Shortest Path Algorithm in Python

Dijkstra Shortest Path algorithm is a greedy algorithm that assigns cost to each adjacent nodes by choosing the minimum element and finds the shortest distance from a given node to the terminal node.
In this tutorial you will understand how Dijkstra algorithm works with easy to understand explanation and also how to implement it in python programming.

TimeStamps:

00:00 Introduction

01:57 Dijkstra Algorithm Explanation
17:11 Python Implementation

🔗Important Links:

🌐Join our community:

[scorpionesp]

You sir.. are amazing! Omg.. and the fact that you actually coded the implementation is just golden.

[fazelamirvahedi]

Thanks for this informative tutorial. I've a problem; when I replace for example source and destination nodes in some cases an 'out of index' error occurs with regard to min_heap[0][1]. For example, if the source node be C and the dest node be A the code works but in the reverse mode it doesn't; why?

[hhhapeffects]

it pops an error when i try to use my very graph:
temp = min_heap[0][1]
IndexError: list index out of range

[fcodefcode]

ı am trying to implement but ı am having some problems like sticking in a loop and not traveling all nodes in my graph

[abduljunaid]

Good effort, but it will not work for all situations. Like if I set my source = "D", and my destination = "A" it will generate error, there might be other failed cases as well. I came across this, because one of my clients copied your code. Thinking it was complete, it took me quite some time to understand the bug was in your logic.

[kpancha]

I tried to do this algorithm, but chose the starting node as C, and the ending node as F. I believe in this case, the shortest path would be 6, but when applying this djikstra's, I get trapped at node A. Can you explain why this happens? If I start at C, do I need to know to mark A and B as visited?

[felixvincent]

How do I modify this algorithm so that the algorithm visits all the vertices with shortest path, so for this graph results the Shortest Path: ['A', 'B', 'C', 'D', 'E', 'F']

[dmytrofrolov]

If I introduce the terminal node without neighbours, code crashes with error:
```
current_node = min_heap[0][1]
IndexError: list index out of range
```
For example:
# K is terminal node, algorithm enters it through A->B->K and can't exit because the only neighbour of K is B and B is already in visited list.
graph = {
'A': {'B':4, 'C':4},
'B': {'A':4, 'D':4, 'K':1},
'C': {'A':4, 'D':4},
'D': {'B':4, 'C':4},
'K': {'B': 1}
}
How can we fix it?

[swaniketchowdhury]

This code in not dynamic for 2 reasons, firstly for how you've initialized the node_data, and secondly, how you are running the loop. Through both can be fixed very easily. Overall great video.

[GPlayerHD]

I'm having trouble understanding this. Why when I use this graph:
graph = {
'0': {'1':10, '2':5},
'1': {'2':2, '3':1},
'2': {'1':3, '3':9, '4':2},
'3': {'4':4},
'4': {'3':6},
}



source = '0'
destination = '3'

why does it gives me 13 as the best path and not 9? [0, 2, 1, 3]

[bhargavaa]

I cant understand 35:12 how to access output

[narendrabandi]

Brother... Implement all the graph algorithms in python... So that it will help us a lot...thank you very much for your tutorials.

[ArbreshaAjrulla]

Great explanation! Can i also have the link of source code please?

[kehindeismaila]

how do one implement this code for a directed graph?

[markdarreldelgallego]

Sir may i ask why the node_data[src]["cost"] = 0 has an error. The error is name node_data[src]["cost"] = 0 is not defined how can i fix it sir? Thank you

[laxmikomarraju]

You're really amazing.. I have been following your videos and I see you make things simple :) Appreciated all your efforts ! Thank you 👍

[kuanarxiv]

Nice work on this bro. But have u ever launch this? That's obvious your minheap didn't initialized in a right scope. At the same time, it's also not necessary to heapify if you heappush everytime. I not sure any other errors exist, just review it casually.

[kumaru]

Its really good video. crispy and clear. i have one doubt. for initialization of graph every node is a infinite but travel from A ->B =2 and A -> C =4 . how you have defined this initially. ?

[pkgpkg]

why am i getting key error 'E' at line "cost = node_data[temp]['cost'] + graph[temp][j]"

[luisdato]

Why did you write "if __name__ == '__main__': " in your code? What is its purpose?