Dijkstra's Algorithm

Dijkstra's algorithm is a popular path-finding algorithm, commonly employed to find

single-source shortest paths in a graph with non-negative edge weights.

So, given a weighted graph $G$ and a source vertex $s$ ,
It finds shortest distance $dist [v]$ for every vertex $v$ .

Greedy approach

It always selects the nearest unvisited node to process next, assuming that this local choice will lead to a globally optimal solution

This only works because of the non-negative weights. Assumes that path distance can only increase as more nodes are added. Once you reach a node via shortest path, it is guaranteed that no future path can improve it.

Coding approach

$dist [v]$ maintains current best distance from source $u$ for vertex $v$ .
Keeps a track of vertices for which distance has already been computed, using a priority queue or matrix.
For every vertex essentially, $dist [v]$ maintains an approximation, the "current best" path to it. During processing, it updates $dist [v]$ if shorter path is found.
A $visited [v]$ that marks if the node has been processed, also signifying whether it's distance is finalized. A node is not marked visited until read from the priority queue, at which it is guaranteed that everything leading up to this node is accounted for, and therefore $dist [v]$ at that time must store the best possible path.

Algorithm Psuedo-code

Initialize:
    dist[v] = ∞ for all v
    dist[s] = 0

    priority queue pq
    push (0, s)

while pq not empty:
    (d, u) = pq.pop_front() // min priority = closest

    if u already visited: continue
    mark u visited

    for each edge (u → v) with weight w:
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            push (dist[v], v)

This essentially ensures that all nodes are all processed in the order of their distances from $u$ , automatically building the shortest path.

Why greedy works

Let's assume that we pop a node from the priority queue. This means that $dist [v]$ is finalized, and cannot improve further.

Assume : That $dist [v]$ can improve further.
This means that there must be some node $x$ through which we have a better shorter path. Which would imply that node $x$ is unvisited till now, we have failed to consider it.

But it also means that $dist [x] < dist [v]$ , since $x$ must've been before $v$ , in order to make $dist [v]$ better.

Essentially means that node $x$ should've been popped from the priority queue earlier.
This means that node $x$ must've already been considered before finalizing $u$ .

But that contradicts our initial assumption

Hence, proved by contradiction, greedy actually works.

Time complexity analysis

We have two major operations that contribute to time-complexity.

Extract min : Pick the vertex with smallest current $dist [v]$
Relaxation : Update or relax distances of adjacent vertices, after traveling each node and calculating only minimum distances from the previous nodes each time.

Using array for storing $dist$

$O (V)$ check for finding minimum distance.
Repeated for $V - 1$ vertices, so contribution is $O (V^{2})$
Updating edges : $O (E)$ , since constant time per edge, and order is of $E$ edges.

Total : $O (V^{2} + E) \approx O (V^{2})$

Best for dense graphs when $E \approx V^{2}$

Binary heap

$O (\log V)$ : extracting min from current heap; Repeated $V$ times
$O (\log V)$ : Update existing heap (heapify) after edge relaxation; repeated $E$ times

Total : $O ((V + E) \log V) \approx O (E \log V)$ , since usually $E \geq V$ ; Why?

Fibonacci heap

Theoretical best

Find min : $O (\log V)$
Decrease key : $O (1)$ armortized

Total : $O (V \log V + E)$

Better when $E$ is large.
It has, in general, large constant factors, therefore rarely ever used in practice.