DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master Dijkstra\
The Problem
Given a weighted graph with non-negative edge weights and a source vertex, find the shortest path from the source to every other vertex. BFS cannot solve this because edges have different weights — a path with more edges might be shorter if those edges have small weights.
The Intuition
Imagine you are at a city and want to find the shortest drive time to all other cities. Dijkstra's approach is greedy: always expand the closest unvisited city next. Why does this work? Because all edge weights are non-negative, so once you have found the shortest path to a city, no future discovery can improve it.
Think of it like a spreading wavefront — but instead of spreading at uniform speed (like BFS), it spreads faster along lighter edges.
The Algorithm
- Initialize distances: source = 0, all others = infinity
- Use a priority queue (min-heap) to always process the closest vertex first
- For the current vertex u, examine each neighbor v:
- If
dist[u] + weight(u,v) < dist[v], update dist[v] (this is called relaxation) - Add v with new distance to priority queue
- Repeat until all vertices are processed
Step-by-Step Example
Graph
A --4-- B --2-- E
| | /
2 1 3
| | /
C --5-- D
Find shortest paths from A
Initial: dist = {A:0, B:inf, C:inf, D:inf, E:inf}
PQ = [(0, A)]
Step 1: Process A (dist=0)
Relax A→B: 0+4=4 < inf → dist[B]=4
Relax A→C: 0+2=2 < inf → dist[C]=2
PQ = [(2,C), (4,B)]
Step 2: Process C (dist=2)
Relax C→D: 2+5=7 < inf → dist[D]=7
PQ = [(4,B), (7,D)]
Step 3: Process B (dist=4)
Relax B→D: 4+1=5 < 7 → dist[D]=5 (improved!)
Relax B→E: 4+2=6 < inf → dist[E]=6
PQ = [(5,D), (6,E), (7,D_old)]
Step 4: Process D (dist=5)
Relax D→E: 5+3=8 > 6 → no improvement
PQ = [(6,E)]
Step 5: Process E (dist=6)
No unvisited neighbors.
Final distances from A: {A:0, B:4, C:2, D:5, E:6}
Shortest paths: A→C (2), A→B (4), A→B→D (5), A→B→E (6)
Python Implementation
Example
import heapq
def dijkstra(graph, source):
"""
graph: dict of {node: [(neighbor, weight), ...]}
Returns: (distances dict, predecessors dict for path reconstruction)
"""
dist = {node: float('inf') for node in graph}
dist[source] = 0
prev = {node: None for node in graph}
pq = [(0, source)]
visited = set()
while pq:
d, u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
if v not in visited and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
prev[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, prev
def reconstruct_path(prev, source, target):
"""Reconstruct shortest path from predecessors."""
path = []
current = target
while current is not None:
path.append(current)
current = prev[current]
path.reverse()
return path if path[0] == source else []
# Example usage
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('D', 1), ('E', 2)],
'C': [('A', 2), ('D', 5)],
'D': [('B', 1), ('C', 5), ('E', 3)],
'E': [('B', 2), ('D', 3)]
}
dist, prev = dijkstra(graph, 'A')
print(dist) # {'A': 0, 'B': 4, 'C': 2, 'D': 5, 'E': 6}
print(reconstruct_path(prev, 'A', 'E')) # ['A', 'B', 'E']
C++ Implementation
Example
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int,int> pii;
vector<int> dijkstra(vector<vector<pii>>& graph, int source) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // Skip stale entries
for (auto [v, weight] : graph[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
Time and Space Complexity
- With binary heap: O((V + E) log V) — each vertex extracted once, each edge relaxed once, heap operations are O(log V)
- With Fibonacci heap: O(V log V + E) — theoretical improvement, rarely used in practice
- Space: O(V + E) for graph storage + O(V) for distance array and heap
Why Non-Negative Weights Only?
Dijkstra's greedy property depends on this fact: once a vertex is processed (popped from PQ), its distance is final. This holds because all future paths to it would go through unvisited vertices with equal or greater distance, plus non-negative edges.
If negative edges exist, a longer path through an unvisited vertex could end up shorter. In that case, use Bellman-Ford.
Applications
- GPS Navigation: Finding shortest driving route between locations
- Network routing: OSPF protocol uses Dijkstra for IP routing
- Game pathfinding: A* algorithm is Dijkstra with a heuristic
- Flight booking: Finding cheapest flight connections
- Social networks: Finding shortest chain of connections
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Dijkstra\.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, graphs, dijkstra, algorithm
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsBellman-Ford AlgorithmLearn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDepth-First Search (DFS) AlgorithmMaster DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.GraphsFloyd-Warshall AlgorithmMaster the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.GraphsKruskal\Learn Kruskal\GraphsPrim\Master Prim\