← CSC 212 Data Structures and Algorithms
Graph Representations and Shortest Path Optimization
Notes
Graph Theory Fundamentals and Representations
A graph G is defined by a pair of sets (V, E), where V represents vertices (nodes) and E represents edges (connections between vertices). Graphs model complex interconnected relationships and can be directed or undirected, weighted or unweighted, cyclic or acyclic. Choosing an appropriate internal memory representation directly influences the time and space complexity of graph algorithms.
An adjacency matrix uses a two-dimensional V-by-V array where cell (u, v) stores edge weights. While it permits O(1) edge existence checks, it consumes O(V^2) memory space, rendering it inefficient for sparse networks where edge counts are far lower than the theoretical maximum. An adjacency list represents each vertex as an array of linked chains or dynamic arrays listing only adjacent neighbors. This representation consumes O(V + E) memory space and provides optimal efficiency when iterating over neighboring vertices, which is essential for sparse physical network topologies.
Shortest Path Algorithms and Dijkstra Logic
Dijkstra's algorithm determines the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge costs. It functions greedily by tracking provisional distances to all nodes, using a priority queue (min-heap) to greedily extract the unvisited vertex with the smallest tentative distance. Once a vertex is extracted, the algorithm relaxes all outgoing edges: if the distance through the current vertex improves the shortest known distance to a neighbor, the neighbor's tentative distance is updated. Using an adjacency list and binary min-heap, Dijkstra's algorithm achieves an optimal time complexity of O((V + E) log V).
Practical example
Consider a Kenyan logistics company, such as Sendy or Fargo Courier, dispatching parcel delivery vans across the Nairobi metropolitan road network. Vertices correspond to key delivery hubs: Nairobi CBD, Westlands, Upper Hill, Industrial Area, and Eastleigh. Weighted edges represent real-time traffic travel times in minutes.
Suppose the adjacency list stores the following directed connections: CBD to Westlands requires 15 minutes, CBD to Upper Hill requires 10 minutes, Upper Hill to Industrial Area requires 12 minutes, Westlands to Industrial Area requires 25 minutes, and Upper Hill to Westlands takes 8 minutes. When a dispatcher routes a medical supply vehicle from Nairobi CBD to Industrial Area, Dijkstra's algorithm evaluates routes iteratively.
Starting at CBD (distance 0), the algorithm inspects neighbors Westlands (15) and Upper Hill (10). Upper Hill is extracted first from the min-heap because 10 is less than 15. The algorithm relaxes edges from Upper Hill: reaching Westlands via Upper Hill totals 18 minutes (greater than the direct 15 minutes, so Westlands remains at 15), while reaching Industrial Area via Upper Hill totals 10 plus 12, which equals 22 minutes. Next, Westlands (15) is extracted; its path to Industrial Area yields 15 plus 25, which equals 40 minutes. The algorithm confirms that the optimal path is CBD to Upper Hill to Industrial Area with a total transit time of 22 minutes, allowing dispatch systems to circumvent Nairobi congestion dynamically.
Quiz
1. What is the primary memory advantage of choosing an adjacency list over an adjacency matrix for sparse networks like municipal road systems?
2. Under what specific condition will standard Dijkstra's algorithm fail to produce accurate shortest path calculations?
3. What is the time complexity of Dijkstra's algorithm when correctly implemented with a binary min-heap and an adjacency list?
Sign in to submit and securely grade your quiz.