CODEWITHSUNDEEP
network-programminggraph-algorithm
Gaurav Gandhi
Gaurav Gandhi

Reputation: 163

difference between Bellman Ford and Dijkstra's algorithm

   2           1
1----------2---------4
|          |         |
|3         |3        |1
|    6     |         |
3---------5 ---------

Ok, so this is the graph. My source node is 1 and destination node is 5

My question is.

Are both the algorithms going to give the same output or not? That is, will both return 1->2->4->5? (Except that negative weights are not allowed in dijkstra's)

Thanks in advance for help.

Upvotes: 12

Views: 37861

Answers (3)

Aman Mishra
Aman Mishra

Reputation: 1

Djikstra algorithm is a greedy technique where as for implementing bellmanford algorithm we require dynamic approach.

In djikstra algo, we do relaxation of every node/vertices in a loop where as in bellmanford algo we perform relaxation only|v-1| times .

The Dijkstra algo is suitable for the graph when it's edge-weight are positive, and fails in the case of negative-edged graph where as the bellmanford algo have advantage over djikstra that it can implement even when the edge's weight are assign negatively.

the bellmanford can find whether the graph solution exists or not (ie given directed graph has negative weight cycle or not) where as the djikstra algo fails to do the same.

the time complexity of djikstra algo is O(v^2) when implemented by linear array,O(e.log v)when implemented with binay heap or Fibonacci heap where as bellmanford algo has O(|v| |e|) time complexity .

Upvotes: 0

bnsk
bnsk

Reputation: 131

The vertexes in Dijkstra’s algorithm contain the whole information of a network. There is no such thing that every vertex only cares about itself and its neighbors. On the other hand, Bellman-Ford algorithm’s nodescontain only the information that are related to. This information allows that node just to know about which neighbor nodes can it connect and the node that the relation come from, mutually. Dijkstra’s algorithm is faster than Bellman-Ford’s algorithm however the second algorithm can be more useful to solve some problems, such as negative weights of paths.

Upvotes: 4

nhahtdh
nhahtdh

Reputation: 56829

Bellman-Ford algorithm is a single-source shortest path algorithm, which allows for negative edge weight and can detect negative cycles in a graph.

Dijkstra algorithm is also another single-source shortest path algorithm. However, the weight of all the edges must be non-negative.

For your case, as far as the total cost is concerned, there will be no difference, since the edges in the graph have non-negative weight. However, Dijkstra's algorithm is usually used, since the typical implementation with binary heap has Theta((|E|+|V|)log|V|) time complexity, while Bellman-Ford algorithm has O(|V||E|) complexity.

If there are more than 1 path that has minimum cost, the actual path returned is implementation dependent (even for the same algorithm).

Upvotes: 26

Related Questions