Welcome to this insightful practice-based lesson! Today, we are diving deep into Advanced Graph Algorithms. This is an all-important topic in computer science, as graphs are prevalent in numerous real-world situations, from social networks to computer networks.
Understanding how to traverse, search, and optimize graphs is crucial, particularly when it comes to finding the shortest path between nodes, mapping routes, or determining any associations between specific data points. Let's go!
DFS and Topological Sort
Introduction to Dijkstra's Algorithm
Reconstructing the Path
Let's Get Hands-On!
Don't be afraid if this seems quite abstract at the moment. That's exactly why we run these lessons — to give you the clarity you need.
In the practice exercises ahead, you'll implement Dijkstra’s algorithm in Kotlin and, by doing so, get a clear understanding of how these principles play out in real-world programs. Your job is not just to learn the algorithm but to grasp how simple and elegant solutions can be constructed for seemingly complex problems.
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal
Before we tackle weighted paths, we must understand fundamental traversal and ordering. Depth-First Search (DFS) is a core technique that explores as far as possible along each branch before backtracking. It is typically implemented using recursion or an explicit stack.
A powerful application of DFS is Topological Sort, which is used on Directed Acyclic Graphs (DAGs) to produce a linear ordering of vertices such that for every directed edge u→v, node u comes before v. This is essential for scheduling tasks with dependencies.
Kotlin
fun topologicalSort(graph: Map<String, List<String>>): List<String> { val visited = mutableSetOf<String>() val result = mutableListOf<String>() fun dfs(node: String) { if (node in visited) return visited.add(node) graph[node]?.forEach { neighbor -> dfs(neighbor) } result.add(0, node) // Add to the front of the list after visiting neighbors } graph.keys.forEach { node -> dfs(node) } return result}
Complexity Analysis:
The time complexity of Topological Sort is O(V+E), where V is the number of vertices and E is the number of edges. This is because the algorithm visits each node and explores each edge exactly once.
One of the exciting algorithms we'll be examining is Dijkstra's Algorithm. Named after its inventor, a Dutch computer scientist, Dijkstra's algorithm is a cornerstone for finding the shortest path in a graph with non-negative weights.
The algorithm centers on a priority queue, which ensures that at any given point, the unvisited node with the lowest distance is chosen. The algorithm keeps track of the shortest distance from the start node to all other nodes in the graph using a map, progressively updating the shortest distance for the unvisited nodes.
Here is the implementation of the algorithm in Kotlin:
Kotlin
import java.util.PriorityQueuefun dijkstra(graph: Map<String, Map<String, Int>>, start: String): Map<String, Int> { // Priority queue to hold nodes and their current distances val minHeap = PriorityQueue<Pair<String, Int>>(compareBy { it.second }) minHeap.add(Pair(start, 0)) // MutableMap to store the shortest distance from `start` to each node val dist = mutableMapOf<String, Int>() dist[start] = 0 while (minHeap.isNotEmpty()) { val (u, currentDist) = minHeap.poll() if (currentDist > (dist[u] ?: Int.MAX_VALUE)) continue val neighbors = graph[u] ?: emptyMap() for ((v, weight) in neighbors) { val distance = currentDist + weight if (distance < (dist[v] ?: Int.MAX_VALUE)) { dist[v] = distance minHeap.add(Pair(v, distance)) } } } return dist}
Complexity Analysis:
The time complexity is O((V+E)logV). Using a priority queue (min-heap) allows us to extract the minimum element in O(logV) time. We perform this extraction V times and potentially update distances E times, resulting in the logarithmic factor applied to both vertices and edges.
While knowing the shortest distance is useful, we often need the actual path (the sequence of nodes). To do this, we maintain a previous map to track which node led to the discovery of the shortest path for each destination.
Once the algorithm finishes, we can reconstruct the path by backtracking from the target node to the start node using this map.
Kotlin
fun getShortestPath(graph: Map<String, Map<String, Int>>, start: String, target: String): List<String> { val dist = mutableMapOf<String, Int>().withDefault { Int.MAX_VALUE } val previous = mutableMapOf<String, String?>() val minHeap = PriorityQueue<Pair<String, Int>>(compareBy { it.second }) dist[start] = 0 minHeap.add(Pair(start, 0)) while (minHeap.isNotEmpty()) { val (u, d) = minHeap.poll() if (d > (dist[u] ?: Int.MAX_VALUE)) continue if (u == target) break // Optimization: stop if we reached the target graph[u]?.forEach { (v, weight) -> val newDist = d + weight if (newDist < (dist[v] ?: Int.MAX_VALUE)) { dist[v] = newDist previous[v] = u // Record that we reached 'v' via 'u' minHeap.add(Pair(v, newDist)) } } } // Backtrack from target to start val path = mutableListOf<String>() var current: String? = target while (current != null) { path.add(current) current = previous[current] } return path.reversed()}
Complexity Analysis:
The time complexity remains O((V+E)logV). The path reconstruction phase takes O(V) in the worst case, which is overshadowed by the main Dijkstra search complexity.
