Before diving into Dijkstra algorithm, we will look at how we might solve the shortest path of a DAG. A reasonable algorithm would be BFS. However one of the problems of using BFS is that the shortest path (least number of vertexes from A to B) might not be the shortest weighted path. This means for BFS to work you will have to evaluate all paths…
BFS for shortest path may work for simple graphs. BFS becomes difficult when graph’s edges are weighted and since the shortest paths to a vertex is not equal the shortest path, trying to use BFS to solve shortest path will involve iterative cycles of backtracking of vertexes. (potentially exponential time)
Using BFS to find all paths to find the shortest path does not work for all graphs as we can see using the following example:
- V2 has 2 possible paths
- V4 has 4 potential paths
- V8 has 8 paths and so on…
Trying to use BFS as a brute force algorithm to finding all the paths will give rise to 2^n possibilities (exponential running time). Dijkstra solves this problem by not having to traverse all paths to find the shortest path and the running time of Dijkstra is not a function of the Edge weight.
Negative weighted edges can causes negative weight cycles and result in unresolved paths. This can be seen in the image below. Negative cycles if unhandled by the algorithm can cause infinite undermined paths.
Algorithms such as Dijkstra requires non-negative weighted edges because Dijkstra algorithm assumes that for each cycle of a relaxed edge, the distanced of the path to the node is optimal. A negative edge will invalidate this optimal path and result in an incorrect path.
Algorithms (e.g.: BellmanFord) that do handle negative weight edges can detect negative cycles and are non-greedy algorithms (back tracks visited vertices/edges).
Optimal substructure is proof for why “relaxation” process of Dijkstra is correct.
The Optimal substructure assumes that :
If u to v is the shortest weighted path d(u,v), then subpaths are from u to v are greater or equal to the shortest path. This has to be true because if not, d(u,v) wouldn’t be the shortest path.
Dijkstra starts with all paths as infinity and evaluates connected vertices by the process of relaxation. The relaxation maintains the invariant of the shortest path to the vertex. The algorithm starts with infinity for all vertices and 0 for the source.
Bellow shows a simplified snippet of the the edge relaxation process.
The Dijkstra algorithm uses edge relaxation to find the shortest path to a vertex. The algorithm then selects the vertex with the shortest path as the next node to explore. This process is repeated until all vertexes / edges are explored.
The algorithm works because for each round of relaxation, the lemma of optimal substructure remains true.
Dijkstra starts all vertices from infinity and the source of value 0. The first relaxation occurs at vertex a:
CurrentShortestPath(a), infinity and sum of
CurrentShortestPath(u), 0 and edge(s,a), 1 is less than infinity, a new shortest path is found.
Note that relaxation is commonly used in algorithms other than Dijkstra, for example algorithms to find the shortest path in a Directed Acyclic Graph (DAG) - (Involves topological sort + relaxation of +ve/-ve edges)
The Run time complexity depends on the implementation, but there are 2 operations on a min-heap; extracting the min vertex and updating vertex for each edge.
- Since E is the dominant factor in the algorithm and E is at most V^2 (Matrix of edges (V x V)), Dijkstra can be expressed as O(V^2).