CODEWITHSUNDEEP
algorithmgraph-algorithm
Mayoweezy
Mayoweezy

Reputation: 587

Is Dijkstra's Algorithm symmetrical?

In Dijkstra Algorithm to find the shortest path in a positively weighted graph, can there be a scenario in which the route A -> B does not equal the route B -> A? (A and B are vertexes on a graph). Can you provide an example?

Upvotes: 1

Views: 374

Answers (1)

OmG
OmG

Reputation: 18838

If the graph is not directional, the set of shortest paths from A to B (S_{ab}) is the same as set of shortest paths from B to A (S_{ba}). You can prove it by the contradiction.

Suppose it is not. So there is at least one path P from B to A which is not in the S_{ab}. As the graph is not directional, there is the same path from A to B. If the length of the path is greater than all path in S_{ab}, so it is not shortest path from B to A, as you can return from B to A with one of path in shortest path in S_{ab}.

Also, if the length of P is less than length of paths in S_{ab}, so we can go from A to B with less than the cost of all path in S_{ab}. Hence, P must be in S_{ab} by the definition of the set. But, it is contradicted by the assumption. Hence, it is not possible.

Upvotes: 3

Related Questions