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
Build a route-finding application using graph data structures, Dijkstra\
Project Overview
Every time you open Google Maps, a graph algorithm finds your route. In this project, we model a city as a weighted graph and implement two pathfinding algorithms: Dijkstra (guaranteed optimal) and A* (faster with heuristics). By the end, you will have a working route finder that finds shortest paths between any two locations.
Modeling a City as a Graph
A city map translates naturally to a graph:
- Nodes = intersections or landmarks
- Edges = roads connecting them
- Weights = distance (or travel time)
Example
class CityGraph:
def __init__(self):
self.adjacency_list = {} # node -> [(neighbor, weight), ...]
self.positions = {} # node -> (x, y) for visualization and A*
def add_location(self, name, x, y):
"""Add a location (node) with coordinates."""
if name not in self.adjacency_list:
self.adjacency_list[name] = []
self.positions[name] = (x, y)
def add_road(self, from_loc, to_loc, distance, bidirectional=True):
"""Add a road (edge) between two locations."""
self.adjacency_list[from_loc].append((to_loc, distance))
if bidirectional:
self.adjacency_list[to_loc].append((from_loc, distance))
def get_neighbors(self, node):
return self.adjacency_list.get(node, [])
def get_all_locations(self):
return list(self.adjacency_list.keys())
Building a Sample City
python example
city = CityGraph()
# Add locations with (x, y) positions
city.add_location("Home", 0, 0)
city.add_location("School", 3, 4)
city.add_location("Park", 1, 3)
city.add_location("Mall", 5, 2)
city.add_location("Hospital", 4, 5)
city.add_location("Library", 2, 1)
city.add_location("Station", 6, 0)
# Add roads with distances
city.add_road("Home", "Park", 3.2)
city.add_road("Home", "Library", 2.2)
city.add_road("Park", "School", 2.2)
city.add_road("Library", "Mall", 3.2)
city.add_road("School", "Hospital", 1.4)
city.add_road("Mall", "Station", 2.2)
city.add_road("Mall", "Hospital", 3.2)
city.add_road("Library", "Park", 2.2)Dijkstra's Algorithm: Guaranteed Shortest Path
Dijkstra's algorithm finds the shortest path from a source to all other nodes. It works by always processing the unvisited node with the smallest known distance — a greedy approach that is provably optimal for non-negative weights.
Example
import heapq
def dijkstra(graph, start, end):
"""Find shortest path from start to end using Dijkstra's algorithm."""
# Distance from start to each node
distances = {node: float('inf') for node in graph.adjacency_list}
distances[start] = 0
# Track the path
previous = {node: None for node in graph.adjacency_list}
# Priority queue: (distance, node)
pq = [(0, start)]
visited = set()
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_node in visited:
continue
visited.add(current_node)
# Found our destination
if current_node == end:
break
# Explore neighbors
for neighbor, weight in graph.get_neighbors(current_node):
if neighbor in visited:
continue
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
previous[neighbor] = current_node
heapq.heappush(pq, (new_dist, neighbor))
# Reconstruct path
path = []
node = end
while node is not None:
path.append(node)
node = previous[node]
path.reverse()
if distances[end] == float('inf'):
return None, float('inf') # No path exists
return path, distances[end]
# Usage
path, distance = dijkstra(city, "Home", "Hospital")
print(f"Shortest path: {' -> '.join(path)}")
print(f"Total distance: {distance:.1f} km")
# Output: Home -> Park -> School -> Hospital (6.8 km)
A* Algorithm: Faster with Heuristics
A* improves on Dijkstra by using a heuristic — an estimate of remaining distance to the goal. It explores the most promising nodes first, often finding the answer much faster.
The key formula: f(n) = g(n) + h(n) where:
- g(n) = actual distance from start to n (same as Dijkstra)
- h(n) = heuristic estimate from n to goal
- f(n) = total estimated cost through n
Example
import math
def heuristic(graph, node, goal):
"""Euclidean distance as heuristic (always admissible for road networks)."""
x1, y1 = graph.positions[node]
x2, y2 = graph.positions[goal]
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
def a_star(graph, start, end):
"""A* pathfinding with Euclidean distance heuristic."""
g_score = {node: float('inf') for node in graph.adjacency_list}
g_score[start] = 0
f_score = {node: float('inf') for node in graph.adjacency_list}
f_score[start] = heuristic(graph, start, end)
previous = {node: None for node in graph.adjacency_list}
# Priority queue: (f_score, node)
open_set = [(f_score[start], start)]
visited = set()
nodes_explored = 0
while open_set:
current_f, current_node = heapq.heappop(open_set)
nodes_explored += 1
if current_node == end:
# Reconstruct path
path = []
node = end
while node is not None:
path.append(node)
node = previous[node]
path.reverse()
return path, g_score[end], nodes_explored
if current_node in visited:
continue
visited.add(current_node)
for neighbor, weight in graph.get_neighbors(current_node):
if neighbor in visited:
continue
tentative_g = g_score[current_node] + weight
if tentative_g < g_score[neighbor]:
previous[neighbor] = current_node
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(graph, neighbor, end)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
return None, float('inf'), nodes_explored
# Compare performance
path_d, dist_d = dijkstra(city, "Home", "Hospital")
path_a, dist_a, explored = a_star(city, "Home", "Hospital")
print(f"Dijkstra: {path_d}, distance={dist_d:.1f}")
print(f"A*: {path_a}, distance={dist_a:.1f}, nodes explored={explored}")
Dijkstra vs A*: When to Use Which
| Feature | Dijkstra | A* |
|---|---|---|
| Optimality | Always optimal | Optimal if heuristic is admissible |
| Nodes explored | More (explores uniformly) | Fewer (directed toward goal) |
| Speed | Slower for point-to-point | Faster for point-to-point |
| Memory | O(V) | O(V) |
| Heuristic needed | No | Yes |
| Best for | All-pairs shortest path | Single source-destination |
Rule of thumb: Use Dijkstra when you need distances to ALL nodes. Use A* when you need the shortest path to ONE specific destination.
Adding Traffic and Dynamic Weights
Real route finders account for traffic. We can modify edge weights based on time of day:
python example
def get_travel_time(self, from_loc, to_loc, time_of_day):
"""Get travel time considering traffic."""
base_time = self.get_base_distance(from_loc, to_loc)
# Rush hour multiplier (7-9 AM, 5-7 PM)
if 7 <= time_of_day <= 9 or 17 <= time_of_day <= 19:
traffic_multiplier = 2.0 # Double travel time
elif 10 <= time_of_day <= 16:
traffic_multiplier = 1.2 # Slight traffic
else:
traffic_multiplier = 1.0 # No traffic
return base_time * traffic_multiplierComplexity Analysis
| Algorithm | Time | Space |
|---|---|---|
| Dijkstra (binary heap) | O((V + E) log V) | O(V) |
| A* (binary heap) | O((V + E) log V) worst, much better in practice | O(V) |
| BFS (unweighted) | O(V + E) | O(V) |
Key Takeaways
- Graph modeling is the first step: Identify what nodes and edges represent in your domain
- Dijkstra guarantees optimality for non-negative weights — use it when you need correctness
- **A* trades a heuristic for speed** — with a good heuristic, it explores far fewer nodes
- Adjacency lists are the right representation for sparse road networks
- Priority queues are the engine that makes these algorithms efficient
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Route Finder Using Graphs.
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, projects, route, finder
Related Data Structures & Algorithms Topics
Continue learning this concept
ProjectsAutocomplete System Using TrieBuild a real-time autocomplete system using a trie data structure with frequency ranking, prefix matching, and a complete Python implementation.ProjectsLibrary Management System Using DSABuild a library management system that demonstrates practical use of hash tables for book lookup, BST for sorted catalogs, queues for waitlists, stacks for undo operations, and linked lists for borrow history.ProjectsMini Search Engine ProjectBuild a mini search engine from scratch using an inverted index (hash map), TF-IDF scoring for relevance ranking, and a trie for autocomplete suggestions.ProjectsSocial Network Analysis Using GraphsModel social networks as graphs and implement BFS for degrees of separation, community detection, influence spread simulation, and simplified PageRank.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.