# 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