Advanced Graph Algorithms

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!

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 \rightarrow v$, node $u$ comes before $v$. This is essential for scheduling tasks with dependencies.

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:

import java.util.PriorityQueue

fun 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) \log V)$. Using a priority queue (min-heap) allows us to extract the minimum element in $O(\log V)$ 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.

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) \log V)$. The path reconstruction phase takes $O(V)$ in the worst case, which is overshadowed by the main Dijkstra search complexity.

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.

Ready to dive in? Let's go!