Algorithm - Dijkstra, shortest path

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…

Why not use BFS to find 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:

Image showing why BFS for all paths can lead to O(2^n) runtime complexity.

  • 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 weight edges

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).

Example of Negative weight edges causing negative weighted cycles.

Optimal Substructure

Optimal substructure is proof for why “relaxation” process of Dijkstra is correct.

The Optimal substructure assumes that :

1. Subpaths of Shortest path are shortest paths
2. Triangle equality

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.

δ(u,v)δ(u,x)+δ(x,v)\Large { \delta(u,v) \leq \delta(u,x) + \delta(x,v) }

Triangle Equality

Dijkstra

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.

Example using Dijkstra. Shows relaxation steps for resolving shortest path.

Example using Dijkstra. Showing the how the table updates for each relaxation step.

Bellow shows a simplified snippet of the the edge relaxation process.

1
2
3
4
5
6
7
relax(v) {
// v next vertex, u previous vertex
if (distanceFromStart[v] > distanceFromStart[u] + edgeWeights[v]) {
distanceFromStart[i] = distanceFromStart[u] + edgeWeights[v];
}
}
// ...

Code : Dijkstra - Array implementation

Relaxation

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.

Example graph showing relaxation.

Dijkstra starts all vertices from infinity and the source of value 0. The first relaxation occurs at vertex a:

CurrentShortestPath(a)CurrentShortestPath(u)+δ(s,a)CurrentShortestPath(a) \geq CurrentShortestPath(u) + \delta(s,a)

Since CurrentShortestPath(a), infinity and sum of CurrentShortestPath(u), 0 and edge(s,a), 1 is less than infinity, a new shortest path is found.

CurrentShortestPath(a)=CurrentShortestPath(u)+δ(s,a)CurrentShortestPath(a) = CurrentShortestPath(u) + \delta(s,a)

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)

Time complexity

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.

Implementation min update Overall
Array Θ(V)\Theta(V) Θ(1)\Theta(1) Θ(V.V+E)\Theta(V.V + E)
Binary min-heap Θ(logV)\Theta(\log V) Θ(logV)\Theta(\log V) Θ(VlogV+ElogV)\Theta(V \log V + E \log V)
Fibonacci heap Θ(logV)\Theta(\log V) Θ(1)\Theta(1) Θ(VlogV+E)\Theta(V \log V + E)
  • 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).

Source - Negative edges