Description
Objectives
-
BFS for Shortest Path
-
Weighted graphs and Dijkstra’s algorithm
Please refer to the previous recitation document for DFS(Depth First Search).
The shortest path between two vertices in a graph is the one where the sum of weights of edges in the path is minimal.
BFS for Shortest Path:
BFS(Breadth-First Search) is used to compute the shortest path between any two vertices in an unweightedgraph. In an unweighted graph, thepath lengthis proportional to the number of vertices in the path.
BFS exhausts all possible vertices at a level (say n) before moving on to vertices at a level – n+1. The claim for BFS is that the first time a node is discovered during the traversal, that distance from the source would give us the shortest path for that node.
The same claim cannot be applied for a weighted graph.
The following example will make it more clear.
