11
$\begingroup$

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.

example graph

Improve this question
$\endgroup$

2 Answers 2

Reset to default
19
$\begingroup$

  1. BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first_search

  2. Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F.

  3. 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)

  4. 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ can you elaborate point 4 $\endgroup$
    – user1988876
    Nov 19, 2013 at 23:57
  • $\begingroup$ @User1988876: As a general comment, if you are interested in the reply of Aditya, I would strongly recommend you to upvote his answer (as I actually did). That is usually a good idea in a site such as this. $\endgroup$
    – Carlos Linares López
    Nov 20, 2013 at 20:31
  • 1
    $\begingroup$ Sorry for the late reply. Take any edge of a graph whose weights are small positive (less than k) integers (u,v) of weight, say, 5. Replace the edge u-v with a a path as follows u-uv1-uv2-uv3-uv4-v (uv1 through uv5 are new nodes) with the weight of each edge in between as 1. Do this for every edge. Now that all weights of the resultant graph are 1, you can think of it as an undirected graph with <= k|v| vertices and <= k|e| edges.Use BFS to find the shortest path. In general, this is not better than Dijkstra as the weights can be arbitrarily large and non integral in a graph. $\endgroup$
    – Aditya
    Dec 6, 2013 at 8:50
6
$\begingroup$

While Aditya's response is good I would like to clarify a few points.

Breadth-First Search

Breadth-First Search (BFS) just uses a queue to push and pop nodes to/from. This means that it visits nodes in the order of their depth.

If it happens that the cost of all operators is the same (so that they are considered to be equal to 1), then it is guaranteed to find an optimal solution.

As a consequence, note the following:

  1. It just enumerates paths until the solution is eventually found. It cannot be said that this algorithm computes the shortest path from the source node to the goal node (period!). It just computes the distance to all paths it encounters on its way towards the goal. In other words, whatever is said of the path it finds to the goal node can be equally said of any other path discovered by it.

  2. Nothing prevents BFS to be applied to graphs with arbitrary costs. The only point to remember is that the algorithm preserves completeness (so that it is guaranteed to find a solution) though admissibility is lost (i.e., it does not guarantee the solution found to be optimal).

  3. Originally, BFS did not consider a CLOSED list to store all the expanded nodes so that you are somehow right when you say that it might fall in a cycle. However, since it explicitly stores all nodes in memory and the more memory demanding layer is always the latest one, BFS is usually extended with a CLOSED list that stores all nodes previously expanded. If a transposition is encountered before expanding a node it can be safely skipped.

Dijkstra's algorithm

In fact, if you add a CLOSED list to BFS as suggested in point 3 above and also sort nodes in the stack (the so-called OPEN list) in ascending order of $g(n)$ (i.e., the cost of the path from the start state to $n$) then you have Dijkstra's algorithm (well, there is also another very important difference, while BFS stops when generating the goal node, Dijkstra's stops when expanding it).

So:

  1. Again, this algorithm just enumerates paths until the solution is eventually found. It is not true that it visits all nodes in the state space and indeed, Dijkstra's algorithm is known to be complete (i.e., it guarantees that a solution will be found if any exists) even if the underlying graph is infinite.

  2. You can safely apply Dijkstra's algorithm when operations have arbitrary costs. Indeed, that's the reason why you substituted the queue with a heap where nodes are inserted in ascending order of their cost.

  3. Edgar Dijkstra originally considered using a CLOSED list (you can check his paper, it is only a few pages long and very easy to read) so that cycles are properly considered.

Hope this helps, maybe a more detailed explanation of these algorithms is needed. If so, do not hesitate to ask for them

Cheers,

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.