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!
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!
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).
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.
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.
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.
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.
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?
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.
@@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?
@@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).
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.
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.
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.
