How Dijkstra's Algorithm Finds the Fastest Route

Note that the direct Hostel to Library path takes 4 mins which is not the fastest way to the Library. Going via the Canteen takes 2 + 1 = 3 minutes. The use of an algorithm is to discover this kind of thing systematically.

THE CORE IDEA

Dijkstra is a greedy algorithm. It maintains a "best known distance" for each building, initially infinite for all but the source. Then it again goes through two steps:
Firstly, it Chooses the unvisited building with the smallest known distance. Mark it final.
Later, Relax the outgoing edges. Ask each neighbor “Is it shorter to go through this building than the best route I already know? If so, then update the distance.
Distance is always only an upper bound that is continuously improved until it is precise.

WHY THE GREEDY CHOICE?
This confirms Dijkstra's accuracy instead. For instances, the earliest building that hasn't been visited is X, located 5 units away. Is it possible for an alternative path to arrive at X in under 5? That path would need to go through a different unvisited building initially, and each unvisited building is already a minimum of 5 away. Adding such additional non-negative edge weights can only increase the total. Thus, X's distance cannot be enhanced, and it is secure to conclude. A negative edge afterward might reduce a distance we've already stated as final, causing the entire proof to fail.

EXAMPLE:
Working out the diagram given:

1. From the Canteen, the Library decreases from 4 to 3 (2 + 1).
2. In the Library, Admin enhances from 10 to 8 (3 + 5). The direct Admin to Canteen edge (2 + 8 = 10) fails.
3. From Lab, the Hall improves from 14 to 13 (10 + 3), beating the Admin to Hall edge (8 + 6 = 14).

To recover the actual route, store a parent pointer whenever a distance improves, then walk backwards from the Hall: Hall ← Lab ← Admin ← Library ← Canteen ← Hostel.

The final answer is 13 minutes.

IMPLEMENTATION
pseudocode:

dist[all] = ∞;  dist[source] = 0
push (0, source) into min-priority-queue
while queue not empty:
    (d, u) = extract-min
    if d > dist[u]: continue          # stale entry
    for each (v, w) in neighbours(u):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u
            push (dist[v], v)

COMPLEXITY ANALYSIS
Let V be the number of vertices and E the number of edges.

The algorithm needs memory for three things:

The graph: storing all the buildings and paths takes O(V + E) space.
The distance and parent tables: one entry per building, so O(V).
The priority queue: in the heap version, the same building can be added more than once (each time we find a shorter route to it), so the queue can hold up to O(E) entries.

Added together, the total is still O(V + E).

Sparse map (limited routes): an actual road network resembles this. Every intersection links to just 3 or 4 streets, regardless of the city's million intersections. Scanning a million structures each time would be excruciatingly slow, so the heap prevails.

Dense map (numerous paths): picture a university with 100 structures where each building connects directly to all the others. There are numerous ways to handle things here, so the additional bookkeeping by the heap hardly saves anything. A basic array is equally effective and simpler to create.

REAL WORLD APPLICATION

• Network routing (OSPF, IS-IS): Each router gets a picture of the network and uses Dijkstras algorithm with link costs as weights to build its forwarding table. Every router gets a picture of the network and uses Dijkstras algorithm with link costs as weights to build its forwarding table.

• Navigation applications: With millions of nodes in road networks, standard Dijkstra is excessively slow. Production systems employ enhancements like A* (which incorporates a goal-oriented heuristic) and contraction hierarchies (which set up shortcuts in advance). Both are based directly on Dijkstra's concept.

• games and robotics : finding a path on a grid or using navigation meshes often relies on algorithms like Dijkstra or A*. These algorithms helps the characters and robots move around obstacles efficiently.

• Logistics and flight planning: By considering costs like fuel, fares, or delivery times as factors, the algorithm determines the most economical path between two points.

LIMITATIONS AND ALTERATIONS
Dijkstra does not work when there are edge weights because of the greedy proof mentioned earlier. Bellman‑Ford handles negative edge weights. Can find negative cycles and it does this with a cost of O(VE). If you want the paths, between every pair of nodes, Floyd‑Warshall which runs in O(V³) is usually the best option. When you have a destination and a reliable distance estimate A* reaches that destination faster because it explores fewer nodes.

CONCLUSION
Dijkstras algorithm works because there is one rule: the nearest node that has not yet been visited can never be made better. Dijkstras algorithm uses adjustment to tighten distances. Dijkstras algorithm keeps the selection cheap with a heap. Dijkstras algorithm gives a best route in O((V + E) log V) time.