Breadth First Search - Finding Shortest Paths in Unweighted Graphs

An introduction to finding shortest paths in unweighted graphs using breadth first search.
Timestamps
------------------------------------------------
0:00 - Introduction
2:11 - Breadth First Search
5:58 - Example walkthrough
12:26 - Extracting a path from the results

[@AdityaSingh-ql9ke]

Seriously, there is not a single video for this fundamental concept on the entire youtube, Thanks a lot ma'am.

[@maryelainecaliff]

You are certainly welcome.

[@NoName-ef2gv]

This is the single most helpful video on the internet! Saved to my algorithm list for future use. Thank you so much!

[@niranjanm5942]

Explained in a way that's very easy to understand and thanks for not giving the code. Now I can try it on my own and test my understanding

[@maryelainecaliff]

That's my goal. I'm glad you found it helpful.

[@ethanmartin942]

Extremely helpful, best guide like this on the internet

[@maryelainecaliff]

Thank you. I appreciate the kinds words.

[@migzleon4047]

Thank you for sharing knowledge with the world...

[@mlevy5722]

Excellent lecture, the best presentation I've seen so far, so clear and very well documented. I also really like the algorithm you derived as it goes beyond the simple BFS. Thank you Dr Califf!

[@maryelainecaliff]

I appreciate the compliment, and I'm very glad you found it helpful. It is certainly true that the fundamental algorithm then applies to many different approaches to searching a graph (or a tree).

[@user-rz1uf7dn3t]

Good lecture! A very good explanation indeed. 13:35 From the start of making the path you can just write from the end to the start of the path array, which saves processing time.

[@hanthedeveloper5900]

thank u very much for your video ma'am, very very simple to understand

[@alifarah9]

thank you professor! keep going :)

[@mehedihasanshameem5347]

take love from Bangladesh

[@jp46614]

Amazing explanation thank you very much! I'm actually learning this for a question to get a potential job at Google 😅 (for context the problem involves turning a chess board into a graph and finding the minimum moves from one position to another) I understand graphs and breadth first search in unweighted graphs now completely!

[@maryelainecaliff]

I'm glad you found it helpful. Good luck with your interview.

[@socksforfrogs]

Super helpful, thank you so much :)!!!

[@maryelainecaliff]

I'm glad to hear it.

[@brunoa.colturato5868]

Wonderful lecture. Thanks a lot.

[@maryelainecaliff]

I'm glad you found it helpful.

[@LowescC]

many thanks...

[@yashwani8155]

excellent !!!

[@ryanqway8560]

Thanks for the video. How are you storing from, to and cost in the queue. A struct or object?

[@maryelainecaliff]

It would depend on the language. Personally, in C++, I would use struct, because an object would be overkill in my opinion.

[@sarahebal4391]

Thank you, professor! I want to use another method than BFS and DFS to find a set of feasible paths (not all the possible paths) between two nodes in a graph do you have recommendations for me?

[@maryelainecaliff]

You might consider some sort of priority queue-based approach, inspired by Dijkstra's but putting everything in the priority queue, even after you have found the best path. That would allow you to explore systematically from less to more expensive taking edge weights into account. If you have cost estimates, you could even do something A* inspired, just again including the alternate path in the search process.

[@sarahebal4391]

@@maryelainecaliff Thank you Prof, for responding, in my problem the graph is weighted, and the cost of edges and nodes has a non-linear function to the amount of flow, this later is not determined in the first step, in this case, how can I get the set of feasible paths?

[@maryelainecaliff]

@@sarahebal4391 To answer that would require quite a bit information about the specifics of the problem (and I unfortunately don't have the time to address more than general problem solutions here, since I still have a full group of my own current students to support).

[@mugheesmb6694]

hey..! how can we know if the graph is weighted or unweighted??? explain please..! i also search on google but cant understand...!

[@maryelainecaliff]

As you look at the drawing of a graph, it's weighted if there are numbers associated with the edges and unweighted if not. When we represent the graph in a computer, for an adjacency list, we'll include a weight for each edge if it's weighted and not otherwise. In an adjacency matrix, the values of cells that represent existing edges will always be 1 in an unweighted graph, but will be the weight if the graph is weighted.
Note that when we think about shortest paths, we're sometimes interested in the unweighted shortest path (the number of edges) even in graphs that do have weights. This can particularly be true when the weights represent something different from cost or distance (for example in a network flow problem).
At some point I hope to post some videos on graph representations and on network flow, but that may be a few months yet.

[@hikari._.zasureiya1540]

thanks professor it helped

[@maryelainecaliff]

Glad to hear it!

[@abrahamberhe2061]

Great video, but how do you track the cost when implementing this?

[@maryelainecaliff]

In BFS, cost is simply the number of edges. You can keep track and store it in an array as you would for Dijkstra’s as shown here or simply count the number of edges in the path.

[@guneetkaur__]

Thanks

[@maryelainecaliff]

Welcome

[@youssefgbb]

How do I apply BFS in weighted graphs?

[@maryelainecaliff]

In exactly the same way. Breadth first search doesn't look at the weights it what it is doing. If you're wanting to find the shortest weighted path, then you want to take a look at Dijkstra's algorithm.

[@youssefgbb]

@@maryelainecaliff Thanks for the quick answer, so can't i use BFS in weighted graph to find the shortest weighted path ?

[@maryelainecaliff]

@@youssefgbb No. By definition, BFS is working with the number of edges, not anything to do with the weights on them.

[@youssefgbb]

Thank you so much Mary I get it.

[@LUONGVANTUTE]

very good lecture. but can you show me the code please?Thank you so much!

[@maryelainecaliff]

I understand the desire for code, but the goal of these particular videos is to help people understand the algorithm well enough to write the code themselves using whichever graph representation is appropriate and whatever language they are working in. I will note that there is some pseudocode here.

[@gurukarthikc7870]

I think there are some mistakes in this video..... Like before analyzing G, B must be analysed as the Queue order is C,B. Meaning after C, B has to be analyzed but the author went with G.

[@maryelainecaliff]

The way the items were placed in the queue was C then G then B (just following the picture from top to bottom there). There is certainly an argument for having put the edges in order B, then C, then G, but if the graph was stored in an adjacency list, there's reason they could be in order AC, then AG, then AB. Certainly if C comes before B, there's no reason that G can't also come before B.
If you do see some actual mistakes, I would very much appreciate learning of them.