Dijkstra Algorithm
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
import java.util.*;
/*
* ============================================================================================
* PROBLEM: Dijkstra's Shortest Path
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given a weighted undirected graph with A nodes (0 to A-1) and M edges.
* Find the shortest distance from a source node C to all other nodes.
* * Rules:
* - If a node is unreachable, return -1 for that index.
* - Edge weights are non-negative.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Dijkstra's algorithm uses a greedy approach to explore the graph.
*
* Step 1: Initialization
* - Create a distance array dist of size A, initialized to Infinity.
* - Set dist[C] = 0.
* - Initialize a Min-Priority Queue to store pairs of {distance, node}.
* - Add {0, C} to the Priority Queue.
*
* Step 2: Relaxation
* While the Priority Queue is not empty:
* 1. Extract the node u with the minimum distance d.
* 2. If d > dist[u], skip this entry (it's a stale record).
* 3. For each neighbor v of u with edge weight w:
* - If dist[u] + w < dist[v]:
* - dist[v] = dist[u] + w (Relaxation step).
* - Add {dist[v], v} to the Priority Queue.
*
* Step 3: Finalization
* - Replace all Infinity values in dist with -1.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= A <= 10^5
* 1 <= M <= 2 * 10^5
* 0 <= weight <= 10^3
*
* Time Complexity:
* O((V + E) log V)
* - Each edge is relaxed at most once.
* - Each node is added/removed from the Priority Queue (log V).
*
* Space Complexity:
* O(V + E) - Adjacency list and distance array.
*
* ============================================================================================
/
public class DijkstraAlgorithm {
public int solve(int A) {
// TODO: Implement solution
return 0;
}
public int[] solve(int i, int[][] edges3, int i1) {
return new int[0];
}
}