2

Dijkstra's has a running time for O(|E| + |V|log|V|) And a brute force BFS has a running time of O(|E| + |V|)

So why is dijkstra's more optimal? It seems that it has a higher running time.

EDIT: Please see the marked answer. Turns out my running time analysis for shortest path using BFS on a weighted graph (basically brute force) is incorrect. Using brute force BFS on a weighted graph has a upperbound of O(V!). Dijstra's is more optimal.

samol
  • 18,950
  • 32
  • 88
  • 127
  • Possible duplicate of [Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?](https://stackoverflow.com/questions/3818079/why-use-dijkstras-algorithm-if-breadth-first-search-bfs-can-do-the-same-thing) – eesiraed Feb 03 '19 at 01:47
  • ...maybe it is "more optimal"(who claimed this?), because it *includes* BFS(visits all reachable nodes in bfs manner) and *additionally* finds shortest paths. – xerx593 Feb 03 '19 at 02:21

2 Answers2

4

Dijkstra's has a running time for O(|E| + |V|log|V|) but it can find shortest path between source and target node in a weighted graph. BFS has a running time of O(|E| + |V|) but it only finds shortest path between source and target node when all your edge have equal weight. If all your edge have same weight, there is indeed no need to run Dijkstra.

xashru
  • 3,400
  • 2
  • 17
  • 30
  • I am trying to understand why you cannot use BFS for weighted graph search. Let's say each time keep track of the current path cost sum and I keep exploring each I try all possible combination of routes. I can eventually find the shortest path with BFS? No? – samol Feb 03 '19 at 14:46
  • @samol: You can certainly extend BFS that way, but then it will no longer have a worst-case running time of O(|E| + |V|). Plain BFS visits each node only once, because the first visit is the shortest path, so you can mark the node as visited and skip it thereafter. If you add logic to re-visit a node every time you find a lower-cast path, it becomes *much* more expensive. The version of Dijkstra's algorithm that's worst-case O(|E| + |V| log |V|) is just BFS with a min-heap instead of a queue, which lets it support weighted edges while still only needing to visit each node once. – ruakh Feb 04 '19 at 23:49
2

I assume that you mean by brute force all combinations of paths and choose the fastest. But this requires you to use BFS (probably) an exponential amount of times and in that case you can't say that the time complexity is O(|V|+|E|). O(|V|+|E|) is if you use BFS a constant amount of time. I mention 2 examples of graphs in order to illustrate the amount of possibilities of paths you have to show that Dijkstra is faster than the brute force BFS, because the latter depends on how many possibilities for paths you have.

A balanced binary tree with a root (starting point) and each vertex having 2 children except the leafs and the destination vertex as one of the leafs. If you start at the root, you have 2 choices for the paths. If you go to one of them, you have further 2 choices and so on, until you are at the destination vertex. This makes 2 * 2 * ... * 2 path possibilities, where it's multiplied log(|V|)-1 times. Which is O(n). This gives the brute force BFS algorithm a running time of O(n^2 + nm) which is slower than Dijkstra.

The full graph: Assuming that you start at V1 and the destination is Vn, you can start at V1 and have V-1 possibilities for the next vertex. At the second vertex you have V-2 possibilities, at the third one V-3 and so on until you're at Vn. This makes V-1 * V-2 * ... * 3 * 2 * 1 = O((V-1)!) number of possible paths, which gives the brute force BFS algorithm an exponential running time.

We can see the latter as the upper bound. The lower bound could be a graph which is a path, for which both algorithms need O(n) time. We can conclude, that probably in all occasions, Dijkstra is either faster or as fast as the brute force BFS algorithm.

Said E.
  • 61
  • 6
  • How do you do running time analysis for a brute force BFS? Like if there is an edge for each pair of vertex, then the running time should be O(V^V), because each vertex can connect to each other vertex. But what if there isn't an edge for each pair of vertex. How do you determine the brute force run time? – samol Feb 04 '19 at 16:15
  • It really depends on how your graph looks like. Let's consider a binary tree with n vertices (it's easy to determine the runtime in this case). If you start at the root, you have two options (left child or right child). If you choose one of them, the options have doubled and you are at 4 possibilities and so on, until you've went through the whole tree. This makes 2*2*2*2....*2 log2(n) times. So this makes O(n) paths and you would need to use BFS O(n) times. Now the runtime of this algorithm would become n*(n+m) = n^2 + nm which is way worse than Dijkstra. – Said E. Feb 04 '19 at 16:30
  • For a general graph, i don't know a formula how to calculate the number of paths in it (it would surprise me if there's a way of doing it). But if the bruteforce BFS solution makes the runtime for a simple graph like a binary tree n^2 + nm, then Dijkstra is probably much faster for any graph. – Said E. Feb 04 '19 at 16:33
  • For a general graph, if let's say each vertex has an average of k edges and N vertices. It would be k^N. Is my analysis correct? In other words, a binary tree is just a graph with average of 2 edges and has a running time of 2^N. And if it is fully connected graph, it would be N^N because there are N edges per vertex – samol Feb 04 '19 at 16:35
  • No, for example for the binary tree (balanced), there are O(n) paths from root to a leaf. O(n) because 2^(log(n)-1) = O(n) because the height of the tree is not n, but log(n). But this for paths from root to leaf, for other pairs, you have less paths. And for a tree in which every vertex has exactly K children, you have K^(log(n)-1) which should be again O(n). Maybe my statement about exponential amount of possibilities isnt correct, but the brute force algorithm is still slower than Dijkstra. – Said E. Feb 04 '19 at 16:56
  • Got it. So there is no universal way to analyze the running time. So I can only estimate the upper bound. And so the running time is worst if each vertex is connected to each other vertex. Which has a O(V^V). And obviously, if the graph was in a different format like binary tree, it will be O(V) – samol Feb 04 '19 at 21:52
  • As far as I know it is like that. I didn't calculate the runtime O(V^V) for the complete graph, i don't know how i would do this precisely. But if I had to guess, I would say (V-1)!, because: Lets assume you start at vertex V1 and want to go to Vn. At V1, you have V-1 possibilities to choose. Lets say you choose one direction and are at V2. At V2, you only have V-2 possibilities, because if you go back to V1, it's not a path anymore (because paths are acyclic). And so on, this makes: V-1 * V-2 * ... * 3 * 2 * 1 until you're at Vn. But I'm not 100% sure, because not all paths must have length n – Said E. Feb 04 '19 at 23:18
  • Got it. Could you summarize your comments into your answer so that I can mark it correct? – samol Feb 04 '19 at 23:19
  • Thank you! marked it as correct. Your answer was really helpful in that it helped me realize that my running time analysis for BFS was incorrect for weighted graphs – samol Feb 05 '19 at 02:57
  • Wait. Last question. Why is the balanced binary tree running time O(n^2 + nm). Shouldn't it be O(n)? N is number nodes. What is M? Since there are a total of O(N) possible paths. All I need to do is to iterate through all the possible paths and find the cheapest. Correct? – samol Feb 05 '19 at 04:27
  • Wouldn't the correct analysis for balanced binary tree be this. There are O(n) paths. For each path, we will need to take log(n) steps (because that is the height of the tree). Hence, the running time is O(n * log(n)) and that allows me to find the shortest path? – samol Feb 05 '19 at 04:36
  • Sorry I didn't mention what I mean by m. m = |E| and refers to the amount of edges. For the balanced binary tree it would need O(n^2 + nm) because for BFS you need O(n+m) and for O(n) times executing the BFS would be O(n*(n+m)) = O(n^2 + nm). – Said E. Feb 05 '19 at 06:49
  • You wrote "There are O(n) paths. For each path, we will need to take log(n) steps (because that is the height of the tree). Hence, the running time is O(n * log(n))". If you use BFS, it doesn't matter (complexity-wise) how long the path is, BFS needs O(n+m) runtime. And if there are O(n) paths, then the brute force BFS (trying all paths and choosing the best one) would need to do O(n) times BFS. That gives us O(n^2 + nm). – Said E. Feb 05 '19 at 06:57