supposedly for some graphs there exists valid shortest path lengths between two nodes of the graph that cant be constructed by breadth first search. what defines these shortest paths that breadth first search cant reach?
2
-
1$\begingroup$ Weighted graphs. BFS is only guaranteed to find shortest paths on unweighted graphs. You should review shortest path algorithms and BFS. $\endgroup$– ryanCommented Apr 25, 2019 at 1:04
-
$\begingroup$ Are you looking for, given an unweighted graph and a path between two nodes, an algorithm to determine whether there is a way to assign weights to all edges so that that path becomes the shortest path between the two nodes but a breadth first search from one of the nodes cannot find that path? $\endgroup$– John L.Commented Apr 25, 2019 at 4:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
BFS doesn't work well on graphs with weighted edges, or in other words, graphs where the cost to travel each edge isn't equal. The reason for this is that BFS implicitly assumes equal path lengths. At each step, all nodes adjacent to the current node get pushed into the queue, regardless of the edge weights. This results in a situation where the number of edges traveled, rather than any actual edge weights, reflects the "path length".
For example, consider a graph with 3 nodes A, B, and C; the edge from A to B AB's weight is 2, BC's weight is 3, and AC's weight is 100. Since A is 2 edges (AB, BC) away from C by taking the path through B, but only 1 edge away from C by taking edge AC, BFS would choose AC as the "shortest path" even though it's weight is significantly higher than the sum of AB and BC.
Instead, try algorithms such as Dijkstra's and Bellman-Ford that explicitly take into account the edge weights (e.g. with a priority queue in Dijkstra's). They tend to have a greater time complexity, but will return the correct answer.
