Dijkstra

Dijkstra's Shortest Path Algorithm

Problem Description

Implement Dijkstra's algorithm to find the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

What is Dijkstra's Algorithm?

Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. It works by iteratively selecting the vertex with the minimum distance and updating its neighbors.

Characteristics

• Time Complexity: O((V + E) log V) with min heap
• Space Complexity: O(V)
• Requirement: Non-negative edge weights
• Strategy: Greedy approach
• Use Case: Single-source shortest path

How It Works

1. Initialize distances: 0 for source, ∞ for others
2. Use a priority queue (min heap) to track vertices by distance
3. While queue is not empty:
   • Extract vertex with minimum distance
   • For each neighbor, try to relax the edge
   • If new distance is shorter, update and add to queue
4. Repeat until all vertices are processed

Key Concepts

Relaxation: Updating the shortest distance to a vertex

if (dist[u] + weight(u,v) < dist[v]):
    dist[v] = dist[u] + weight(u,v)
    parent[v] = u

Your Task

Implement the following methods in Dijkstra.java:

1. shortestPath(Graph graph, int source) - Find shortest distances
2. getPath(Graph graph, int source, int dest) - Reconstruct path

Test Cases to Consider

• Simple graph with few vertices
• Graph with multiple paths (ensure shortest is found)
• Source equals destination
• Unreachable vertices
• Graph with all equal weights
• Large graph performance

Hints

• Use PriorityQueue<int[]> where int[]{vertex, distance}
• Use HashMap to store distances
• Use another HashMap to store parent pointers for path reconstruction
• Mark vertices as visited or use distance checks
• For path reconstruction: backtrack from destination using parents

Algorithm Pseudocode

function Dijkstra(graph, source):
    dist[source] = 0
    for each vertex v in graph:
        if v != source:
            dist[v] = INFINITY
    
    pq = PriorityQueue()
    pq.add((source, 0))
    
    while pq is not empty:
        (u, current_dist) = pq.extractMin()
        
        if current_dist > dist[u]:
            continue
        
        for each neighbor v of u:
            alt = dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] = alt
                parent[v] = u
                pq.add((v, alt))
    
    return dist

Visual Example

Graph:
  A --1-- B
  |       |
  4       2
  |       |
  C --1-- D

Starting from A:
Step 1: dist[A]=0, visit A, update B(1), C(4)
Step 2: visit B, update D(3)
Step 3: visit D, update C(3)
Step 4: visit C

Final: A(0), B(1), C(3), D(3)

Applications

• GPS navigation (shortest route)
• Network routing protocols
• Social network (shortest connection)
• Flight itinerary planning
• Computer networks (packet routing)
• Resource allocation

Why Priority Queue?

• Need to always process vertex with minimum distance
• PriorityQueue gives O(log V) for insert/extract
• Alternative: linear search would be O(V²)

Dijkstra vs Bellman-Ford

Aspect	Dijkstra	Bellman-Ford
Weights	Non-negative only	Any weights
Time	O((V+E) log V)	O(VE)
Negative cycles	No	Detects
Approach	Greedy	Dynamic Prog

Follow-up Questions

1. How would you modify this for negative weights? (Hint: Bellman-Ford)
2. How would you find k shortest paths?
3. Can you optimize for sparse graphs?
4. How would you handle dynamic graphs (edges added/removed)?

Common Pitfalls

• Not handling unreachable vertices
• Using wrong data structure (not priority queue)
• Forgetting to check if new distance is actually shorter
• Processing vertices multiple times
• Not initializing distances correctly

Optimizations

1. Bidirectional search: Search from both ends
2. A algorithm*: Add heuristic for goal-directed search
3. Lazy deletion: Don't remove from PQ, check on extraction
4. Fibonacci heap: Improve to O(E + V log V) theoretically

Edge Cases

• Source equals destination (distance = 0)
• Unreachable vertices (distance = ∞)
• Single vertex graph
• Self-loops
• Multiple edges between vertices

Path Reconstruction

function reconstructPath(parent, dest):
    path = []
    current = dest
    while current is not null:
        path.add(current)
        current = parent[current]
    reverse(path)
    return path

Related Algorithms

• Bellman-Ford (handles negative weights)
• Floyd-Warshall (all pairs shortest path)
• A* (with heuristic)
• Bidirectional Dijkstra
• Johnson's algorithm

Practice Problems

1. Network Delay Time
2. Cheapest Flights Within K Stops
3. Path With Minimum Effort
4. Minimum Cost to Reach Destination
5. Shortest Path with Alternating Colors