Difference between DIjkstra and BellmanFord algorithm [closed]

Question

I am wring thesis about shortest path algorithms. And i don't understand one thing...

I have made visualisation of dijkstras algorithm. 1) Is it correct ? Or am i doing something wrong? 2) How would look Bellman-Ford algorithm? As fas as i have looked for difference, i found "Bellman-ford: the basic idea is very similar to Dijkstra's, but instead of selecting the shortest distance neighbour edges, it select all the neighbour edges." But also dijkstra checks all vertexes and all edges, isnt it?

Answer 1

dijkstra assumes that the cost of paths is montonically increasing. that plus the ordered search (using the priority queue) mans that when you first reach a node, you have arrived via the shortest path.

this is not true with negative weights. if you use dijkstra with negative weights then you may find a later path is better than an earlier one (because a negative weight improved the path on a later step).

so in bellman-ford, when you arrive at a node you test to see if the new path is shorter. in contrast, with dijkstra, you can cull nodes

in some (most) cases dijkstra will not explore all complete paths. for example, if G linked only back to C then any path through G would be higher cost that any through C. bellman-ford would still consider all paths through G to F (dijkstra would never look at those because they are of higher cost that going through C). if it does not do this it can't guarantee finding negative loops.

here's an example: the above never calculates the path AGEF. E has already been marked as visited by the time you arrive from G.

Answer 2

I am also thinking the same

Dijkstra's algorithm solves the single-source shortest-path problem when all edges have non-negative weights. It is a greedy algorithm and similar to Prim's algorithm. Algorithm starts at the source vertex, s, it grows a tree, T, that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the vertex closest to S, then the next closest, and so on.