# Lesson 5 - Graph Algorithms (BFS, DFS & Shortest Paths)

Please visit the Lesson Page for more detailed info

Session Recordings:
English: https://youtu.be/SmOrBW22R2k
Hindi: https://youtu.be/avSKR73MqBE

In this lesson, we look at the graph data structure and implement common graph algorithms like breadth-fist search, depth-first search, and shortest paths.

### Notebooks used in this lesson:

Hi, the notebook is not updated with the lecture material. Seems Aakash forgot to commit the notebook. Can we have the codes recreated in the notebook, please?

3 Likes

Hello, The notebook linked from the lesson page contains all the code, please go through it.

1 Like

Has anybody done the DFS Exercises? I’m trying to get the parent of DFS nodes! not sure if it’s correct! I write code parent=current aftet popping it!

current=stack.pop()
parent=current

so it gives me this! is it right!??
should i write…
parent.append(current) after popping!!(then it gives long list!)

1 Like

I have done it like this and it gives correct result…

Hope it helps…

1 Like

Has anyone implemented this…

My only breakthrough is that if `len(edges) > num_nodes` then graph must contain a cycle

1 Like

I am also stuck at he time complexities of DFS and BFS and Dijkstra’s algorithm
Pls can someone explain them ???

1 Like

Thanks for the reply. Yes I figured it out too and sure it helps.

1 Like

I practiced it from This: https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
and from some you tube channel(better to search). it took good amount of time to get the hang of it. but the explanation is good. there’s another way of graph coloring!! i have to check it too.
Oh and yes try to break it the whole code first to understand properly then practice together!

1 Like

Check this out: https://youtu.be/XB4MIexjvY0 for Djikstra’s algiorithm.

1 Like

Thank You very much…I would be checking and learning all of these in a couple of days…
I might become a champion in Graphs becuase of You…Thank You once again Mariha…

1 Like

my repr function for Adjacency Matrix isnt working correctly
i have tried it in two following ways
first

`````` def __repr__(self):
return str([print(self.data[i]) for i in range(self.num_nodes)])
``````

this is giving

``````[0, 1, 0, 0, 1]
[1, 0, 1, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 1, 0, 1, 0]

[None, None, None, None, None]
``````

i want to remove none list
and second

``````def __repr__(self):
for i in range(self.num_nodes):
return str(self.data[i])
``````

and this is returning

``````[0, 1, 0, 0, 1]
``````

hi i came up with this shortest path algo on my own before watching the video

i know this is a stupid question but is this same as Dijkstra’s algorithm. i came up with this after reading the explaination that was given in the jovian notebook.
it is also giving the correct answer so i thought i should confirm with some expert

in the below photo i compared the the time of mine and the given algo in notbook and my algo is certainly faster. so please someone confirm this

this is the link to my notebook

nevermind, i understood what i am missing. correct me if i am wrong but the algo i have written doesn’t give shortest path but follows the path which seems shortest from current node

Hi everyone, I have a question regarding the video of Lesson 5.

At 1:52:47 of the lesson video, I wonder why the algorithm on graph2 returns 15:

shortest_path(graph2, 2, 8)

While graph2 is defined as a undirected graph, the shortest path from 2 to 8 should be 12 (going through 2 → 3 → 0 → 8), instead of 15 (going through 2 → 3 → 4 → 8).

It is also strange that shortest_path(graph2, 1, 2) returns infinity, while shortest_path(graph2, 2, 1) returns 6. For undirected graph it should be the same.

Have anyone checked it out and had an idea of it? Am I understanding it correctly? Thank you for any of your advise.