principleModerate
Dijkstra algorithm vs breadth first search for shortest path in graph
Viewed 0 times
pathdijkstragraphsearchshortestbreadthalgorithmfirstfor
Problem
I have asked this question in StackOverflow. I was asked to move in here. so here it is:
I need some clarifications and inputs regarding Dijkstra's algorithm vs breadth first search in directed graphs, if these are correct.
Dijkstra's algorithm finds the shortest path from Node
but for that, All paths from
BFS: finds the shortest path from node
however, BFS just calculates the path from Node A to Node F and not necessarily all path from Node A.
if Node F is reached early, it just returns the path.
I need some clarifications and inputs regarding Dijkstra's algorithm vs breadth first search in directed graphs, if these are correct.
Dijkstra's algorithm finds the shortest path from Node
A to Node F in a weighted graph regardless of if there is a cycle or not (as long as there are no negative weights)but for that, All paths from
A to all other Nodes in the graph are calculated and we grab the path from A to F by reversing the sequences of nodes in prev.BFS: finds the shortest path from node
A to node F in a non-weighted graph, but if fails if a cycle detected. however, BFS just calculates the path from Node A to Node F and not necessarily all path from Node A.
if Node F is reached early, it just returns the path.
Solution
-
BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first_search
-
Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F.
-
In an unweighted graph, you can use BFS to search for the shortest path from A to all other nodes in the same run too! (just don't make it stop as soon as it finds F)
-
You can use a BFS type algorithm to find the shortest path if you know all lengths are integers less than a 'small' number k in O(k(v+e)) time by replacing every edge (u,w) of length n with a path of n-1 nodes between u and w, the length of each edge in the path is 1.
Hope this helps.
BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first_search
-
Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F.
-
In an unweighted graph, you can use BFS to search for the shortest path from A to all other nodes in the same run too! (just don't make it stop as soon as it finds F)
-
You can use a BFS type algorithm to find the shortest path if you know all lengths are integers less than a 'small' number k in O(k(v+e)) time by replacing every edge (u,w) of length n with a path of n-1 nodes between u and w, the length of each edge in the path is 1.
Hope this helps.
Context
StackExchange Computer Science Q#18138, answer score: 19
Revisions (0)
No revisions yet.