Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dijkstra’s shortest-path algorithm what if there are paths with same distance?

enter image description here

In this network Dijkstra’s shortest-path algorithm is used. The question is which path will A use to reach D because both are equal?

enter image description here

is that table missing?

like image 574
makkuzu Avatar asked Dec 22 '13 17:12

makkuzu


People also ask

Will dijkstra work if all edges have same weight?

Yes dijkstra algorithm can find the shortest path even when all edges have the same weight. dijkstra has time complexity O((V+E)logV). Instead you should choose BFS algorithm to do the same thing,because BFS has time complexity O(V+E),so BFS is asymptotically faster than dijkstra.

What are the limitation of dijkstra's shortest path algorithm?

The major disadvantage of the algorithm is the fact that it does a blind search there by consuming a lot of time waste of necessary resources. Another disadvantage is that it cannot handle negative edges. This leads to acyclic graphs and most often cannot obtain the right shortest path.

Is it possible to find all pairs of shortest paths using Dijkstra's algorithm?

With Dijkstra's Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the "source node") to all other nodes in the graph, producing a shortest-path tree.

Does dijkstra check all paths?

Dijkstra's algorithm in default form computes the shortest distance from a starting node to all connected nodes. Even in this form it does not visit all nodes: only the vertices of a connected component have to be checked.

Do we remove parallel edges in Dijkstra algorithm?

Step 2: Remove all parallel edges between two vertex except the one with least weight. In this graph, vertex A and C are connected by two parallel edges having weight 10 and 12 respectively. So, we will remove 12 and keep 10. We are now ready to find the shortest path from vertex A to vertex D.

Can there be multiple shortest paths?

In general, there can be multiple shortest paths in a graph. In particular, you can use Djikstra's algorithm to compute shortest paths and this algorithm can return multiple paths from any node A to any other node B.


2 Answers

It depends on your actual implementation and the way your input graph was described (e.g. edges can go in different order and this will have an impact on the result if there are many).

However, it's guaranteed that it will find some path which has optimal length.

Your table seems to be wrong at E and F vertices. The parent vertex for E is D (AB->BD->DE = 3 + 4 + 2 = 9), so is for F.

like image 167
dreamzor Avatar answered Oct 11 '22 02:10

dreamzor


It depends on the implementation of the relaxation function. For example, the algorithm described in the wikipedia uses strictly a less-than comparison: if alt < dist[v] so in this case (and all the implementations I've seen) the shortest path from A to D is A -> B -> D.

Why? Because (S = settled nodes and Q = queue of nodes, a pair of distance, parent):

  1. Start relaxing A, so you get the S = {A:0} and Q = {B:3,A C:5,A D:9,A}
  2. From Q select B and relax it. You get S = {A:0 B:3,A} and Q = {C:(5,A) D:7,B E:10,B}
  3. From Q select C and relax it. You get S = {A:0 B:3,A C:5,A} and Q = {D:7,B E:10,B}.
  4. From Q select D and you can finish the algorithm.

Note that in step 3, you don't need to change the parent of D because the new path is not better than the current path. If the relaxation algorithm uses a less-than-or-equal comparison, then the result will be different.

like image 38
Javier Avatar answered Oct 11 '22 03:10

Javier