View the city as an algorithmic map. Each zone is one DAA case study.
City Network Overview
Infrastructure & Network Optimization using core DAA algorithms.
Algorithm Zone
1. Optimal Road Network Construction
Transport Infrastructure · Minimum Spanning Tree · Kruskal + Prim + Union–Find
Problem Context
The city is expanding with several new townships. Each pair of major junctions has an estimated road construction cost (land, materials, labour). If engineers connect junctions in an ad-hoc manner, they may create redundant loops, overspend the budget, and still leave some junctions disconnected.
We need a backbone road layout that connects all junctions with the minimum possible total cost, while guaranteeing that every junction is reachable from every other one.
Algorithmic Solution
The road network is modeled as a weighted, undirected graph G(V, E), where junctions are vertices and candidate roads are edges weighted by construction cost.
- Kruskal’s Algorithm: Sort all edges by increasing weight and add them one by one if they do not form a cycle. Cycle detection is done using Union–Find with path compression and union by rank. Time complexity: O(E log E).
- Prim’s Algorithm: Start from any junction and grow the MST by repeatedly choosing the minimum-weight edge that connects a new vertex to the tree using a min-heap. Time complexity: O(E log V).
Both algorithms should yield the same total cost, which validates correctness.
Input / Output
Input: Junction list and road list with construction costs.
Output: Set of roads forming the MST and the minimum total cost.
Related SDGs
SDG 9.1: Sustainable infrastructure planning.
SDG 11.2: Accessible and connected transport networks.
How This Helps in General
Minimum Spanning Trees are used in power grids, water pipelines, fiber networks, and computer networks to design cost-efficient backbones.
2. Shortest Travel-Time Routing
Commuter Mobility · Dijkstra + BFS (Time-weighted Graph)
Problem Context
During peak office hours, shortest-distance routes are not always the fastest. Narrow roads may be congested, while slightly longer ring roads may provide quicker travel.
Citizens require a routing system that minimises travel time, not physical distance.
Algorithmic Solution
The city is represented as a directed, weighted graph where edge weights represent travel time in minutes.
- Dijkstra’s Algorithm: Computes minimum travel time from a source to all other zones using a priority queue. Time complexity: O((V + E) log V).
- BFS: Used for unweighted pedestrian-only or signal-free subgraphs where all edges have equal travel time.
Input / Output
Input: Road network with time costs and a source zone.
Output: Minimum travel time and path to each zone.
Related SDGs
SDG 11.2: Sustainable urban mobility.
SDG 9.C: Smart transport infrastructure.
How This Helps in General
Shortest-path algorithms are the foundation of navigation systems, logistics routing, and communication networks.
3. Traffic Signal Timing Optimization
Junction Management · Queues · Priority Queue · Efficient Sorting
Problem Context
Fixed and equal green times at a multi-road junction cause inefficient traffic flow. Some directions remain congested while others are underutilised, leading to increased waiting time, fuel consumption, and emissions.
The goal is to dynamically allocate green time based on real-time traffic demand measured as queue length at each lane.
Algorithmic Solution
Each lane at the junction is represented using a queue of vehicles. At the start of each signal cycle, queue lengths are measured.
- Queue lengths are stored in an array and sorted using an efficient algorithm such as Merge Sort or Quick Sort in O(k log k), where k is number of lanes.
- A priority queue (max-heap) can also be used to repeatedly pick the most congested lane in O(log k) time.
- Green time is distributed proportionally: every lane gets a base time, and extra time is allocated according to congestion level.
Input / Output
Input: Queue length per lane and total signal cycle time.
Output: Optimised green time allocation for each lane.
Related SDGs
SDG 11.2: Efficient urban transport systems.
SDG 11.6: Reduced environmental impact of cities.
How This Helps in General
Queue-based scheduling is widely used in CPU scheduling, network packet handling, and call-center optimisation. Priority queues allow fast adaptation to changing load.
4. Emergency Vehicle Fastest Route Planner
Emergency Response · BFS + DFS on Reduced Graph
Problem Context
During medical emergencies or accidents, normal traffic routes may be blocked due to congestion, road work, or accidents. Emergency vehicles must quickly determine which routes are still usable.
Algorithmic Solution
The road network is treated as an unweighted graph after removing blocked edges.
- DFS: Used first to ensure the destination lies in the same connected component as the emergency station.
- BFS: Applied to find the shortest path in terms of number of hops, which approximates the fastest route.
This approach runs in O(V + E) time and is suitable for rapid response.
Input / Output
Input: Road graph, blocked roads, source and destination nodes.
Output: Fastest feasible route or indication that none exists.
Related SDGs
SDG 3: Good health and well-being.
SDG 11.5: Disaster and emergency resilience.
How This Helps in General
BFS and DFS are foundational graph algorithms used in routing, network reliability, and state-space search problems.
5. Water Pipeline Pressure Optimization
Water Distribution · Graph Traversal + Efficient Sorting
Problem Context
In a city’s water distribution network, trunk pipelines feed several residential branches. During peak hours, some tail-end colonies receive very low water pressure, while others receive excess supply. Budget constraints make it impossible to upgrade all pipelines at once.
The objective is to identify the most critical pipelines (bottlenecks) so that upgrades can be prioritised for maximum improvement in water pressure.
Algorithmic Solution
The pipeline network is modeled as a directed graph where nodes represent junctions and edges represent pipelines with capacity constraints.
- DFS/BFS: Used to compute how many consumer nodes depend on each pipeline (downstream demand).
- Each pipeline is assigned a criticality score based on demand-to-capacity ratio.
- Pipelines are sorted using an efficient sorting algorithm such as Merge Sort in O(E log E) time.
The highest-ranked pipelines are flagged as bottlenecks for immediate upgrade.
Input / Output
Input: Pipeline graph, capacities, and consumer demand values.
Output: Sorted list of pipelines by criticality.
Related SDGs
SDG 6.1: Access to safe drinking water.
SDG 9.1: Sustainable infrastructure investment.
How This Helps in General
Combining graph traversal with sorting is a common pattern in infrastructure analysis. Similar techniques are used to prioritise road repairs, power line upgrades, and communication network expansions.
6. Power Grid Load Minimization
Electric Grid · Prim’s MST + Min-Heap
Problem Context
As new residential and commercial areas are developed, they must be connected to the existing power grid. Multiple candidate cable routes exist, each with associated cost and transmission loss.
The goal is to connect all substations and colonies with minimal total cost while ensuring reliable power delivery.
Algorithmic Solution
The power network is modeled as a weighted, undirected graph where nodes are substations and edges are transmission lines weighted by cost and loss.
- Prim’s Algorithm: Grows a Minimum Spanning Tree starting from a chosen substation using a priority queue.
- Each step adds the minimum-weight edge that connects a new node to the tree.
- Time complexity is O(E log V).
The resulting MST represents an efficient backbone for the expanded power grid.
Input / Output
Input: Graph of substations with transmission line weights.
Output: Selected power lines and total grid expansion cost.
Related SDGs
SDG 7: Affordable and clean energy.
SDG 9: Reliable infrastructure.
How This Helps in General
MST-based planning is widely used in designing electrical grids, cable networks, and large-scale distribution systems.
7. Garbage Truck Route Optimization
Solid Waste Management · Dijkstra + Greedy Ordering + Sorting
Problem Context
Garbage collection trucks often follow manually designed routes that are repeated every day without considering changes in traffic conditions or ward layouts. This leads to unnecessary fuel consumption, longer collection times, and uneven service quality.
The objective is to compute an efficient route that visits all pickup points while keeping the total travel distance as small as possible.
Algorithmic Solution
Instead of solving the full Travelling Salesperson Problem (which is NP-hard), a practical approximation strategy is used:
- Dijkstra’s Algorithm: Used to compute shortest path distances between the depot and all pickup points, as well as between pickup points themselves.
- Greedy Nearest-Neighbor Heuristic: Starting from the depot, repeatedly visit the nearest unvisited pickup location.
- Sorting: Candidate next stops can be sorted by distance to speed up selection in O(n log n).
This hybrid approach produces good-quality routes efficiently for small to medium wards.
Input / Output
Input: Pickup locations, depot location, and road network distances.
Output: Ordered garbage collection route and total travel distance.
Related SDGs
SDG 11.6: Efficient waste management.
SDG 13: Reduced emissions through optimised routing.
How This Helps in General
Greedy routing heuristics combined with shortest-path algorithms are widely used in logistics, courier services, school bus routing, and last-mile delivery systems.
8. Public Transport Timetable Generation
Public Transport · Efficient Sorting + Greedy Interval Selection
Problem Context
Urban bus fleets are limited, but the demand for trips is high throughout the day. Poor scheduling can lead to idle buses during peak demand or overlapping assignments.
The goal is to generate a timetable that maximises the number of non-overlapping trips handled by each bus.
Algorithmic Solution
Each candidate bus trip is modeled as a time interval [start, end].
- Trips are sorted by finishing time using an efficient sorting algorithm in O(n log n).
- A greedy strategy selects the earliest finishing trip that does not overlap with the previously chosen one.
This algorithm is optimal for interval scheduling and is simple to implement.
Input / Output
Input: List of bus trips with start and end times.
Output: Maximum set of non-overlapping trips assigned to a bus.
Related SDGs
SDG 11.2: Improved public transport reliability.
SDG 9.4: Efficient use of transport resources.
How This Helps in General
Interval scheduling is used in CPU scheduling, exam timetables, classroom allocation, and reservation systems where resource conflicts must be avoided.
9. Bridge Construction Priority Model
Critical Infrastructure · DFS-Based Bridge Detection
Problem Context
Some bridges and elevated roads are so critical that their failure would disconnect entire regions of the city from hospitals, schools, or business hubs. Identifying such links is essential for maintenance prioritisation.
Algorithmic Solution
The city road network is modeled as an undirected graph. A DFS-based bridge detection algorithm is applied:
- Each node stores discovery time and lowest reachable time.
- An edge (u, v) is a bridge if
low[v] > disc[u]. - Runs efficiently in O(V + E) time.
Bridges are ranked and marked for inspection and reinforcement.
Input / Output
Input: Graph of regions and connecting bridges.
Output: List of critical bridges.
Related SDGs
SDG 9: Resilient infrastructure
SDG 11: Safe and sustainable cities
General Importance
Bridge detection is widely used in communication networks, power grids, and transport planning to identify single points of failure.
10. Flood Evacuation Simulation
Disaster Management · Multi-source BFS
Problem Context
During heavy rainfall, floods originate from rivers or lakes and spread to nearby localities. Authorities need to identify which shelters remain reachable before roads are submerged.
Algorithmic Solution
Flood spread is modeled using multi-source BFS:
- Flood source nodes are inserted into a queue initially.
- BFS levels represent time steps of flood expansion.
- Shelters are marked safe or unsafe based on arrival time.
This ensures optimal time computation in O(V + E).
Input / Output
Input: City graph, flood sources, shelters, time threshold.
Output: Flood arrival times and shelter safety status.
Related SDGs
SDG 11.5: Disaster risk reduction
SDG 13: Climate action
General Importance
Multi-source BFS is used in modeling floods, fire spread, disease outbreaks, and information propagation across networks.
Technical Documentation & SDG Mapping
DAA Portfolio · Algorithms · Data · Complexity
Dataset Design
Each problem uses a structured 20-row CSV dataset mapped directly to algorithm inputs such as nodes, edges, weights, queue sizes, or timestamps.
Efficiency Analysis
Time and space complexity are analysed using Big-O notation. Worst-case scenarios are discussed in plain text aligned with the Design and Analysis of Algorithms syllabus.
SDG Alignment
SDGs covered include 3, 6, 7, 9, 11, and 13. Each algorithm contributes directly to sustainability, resilience, and smart-city planning.
Academic Integrity
All implementations are original C++ programs using STL only. No third-party libraries or frameworks are used.