💻 Shortest Delivery Route with Dijkstra

Uncover the fastest paths in road networks using greedy Dijkstra — input graph edges and endpoints, trace the optimal route!

🚚 The Logistics Manager's Route

🎯 The Challenge:

John, a logistics manager, is tasked with finding the shortest delivery route between two warehouses in a city using Dijkstra's algorithm. The city's road network is a weighted graph.

📋 Problem:

Determine the quickest route (path and distance) from source to destination, or report no path.

Problem Specifications

  • Input: n (1≤n≤100), m (1≤m≤100), m lines u v w (0≤w≤100), src, dest (0≤src,dest
  • Output: "Shortest path: src -> ... -> dest" and "Shortest distance: X", or "No path found".

Example: Input 1

4 5 0 1 2 0 2 4 1 2 1 1 3 7 2 3 3 0 3
Shortest path: 0 -> 1 -> 2 -> 3 Shortest distance: 6

🔄 Dijkstra's Algorithm Strategy

Key Idea

  1. Build adj list from edges.
  2. Init dist[src]=0, others inf; parent[src]=-1; PQ with (0,src).
  3. While PQ not empty: extract min u.
  4. For each neighbor v of u: if dist[v] > dist[u] + w, update dist[v], parent[v]=u, add/update PQ.
  5. Reconstruct path from dest back via parents.

Note: Use heap for PQ. If dist[dest]=inf, no path.

Dijkstra (Heap)

Time: O((V+E) log V)

BFS (Unweighted)

O(V+E) — but weights require Dijkstra

🔍 Step-by-Step Dijkstra Demo

Ready. Use controls below to start demo.

Graph Edges

Current Distances & Parents

Priority Queue (dist, node)

Path will appear here

Progress Tracker

1. Build adj list; init dist/src=0, PQ=(0,src)
2. Extract min u from PQ
3. For neighbors v: relax if better, update parent
4. Add/update v in PQ
5. Repeat until PQ empty
6. Reconstruct path from dest via parents

🎮 Build Your Shortest Route Finder

Enter details and press Find

Examples

Sample 1 (n=4,m=5,src=0,dest=3)
→ 0 -> 1 -> 2 -> 3 (6)
Sample 4 (no path to 4)
→ No path found

📊 Analysis & Optimization

Time

O((V+E) log V)

With binary heap PQ.

Space

O(V + E)

Adj list, dist, parent, PQ.

Optimization Ideas

  • For dense graphs, use adj matrix O(V^2).
  • Since n≤100, simple implementations fine.
  • In C++, use priority_queue>; vector>> for adj.
  • Path reconstruction: backtrack from dest using parents.