HiveBrain v1.2.0
Get Started
← Back to all entries
principleModerate

Dijkstra algorithm vs breadth first search for shortest path in graph

Submitted by: @import:stackexchange-cs··
0
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 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.

Context

StackExchange Computer Science Q#18138, answer score: 19

Revisions (0)

No revisions yet.