Advanced Graph Algorithms: Real-World Problem Solving 🚀

Welcome to the final chapter of graphs! Now that you understand graph basics, representations, and traversal, let’s tackle advanced algorithms that solve real-world problems. We’ll learn shortest path algorithms, minimum spanning trees, and see how graphs power everything from GPS navigation to social networks.

Shortest Paths: Finding the Quickest Route 🛣️

Dijkstra’s Algorithm: GPS Navigation 📍

Imagine you want to find the fastest driving route between cities. Some roads are highways (fast), others are local streets (slow). Dijkstra’s algorithm finds the shortest path considering these different “costs”.

package main

import (
    "fmt"
    "math"
)

// Dijkstra's Shortest Path Algorithm
type DijkstraGraph struct {
    vertices int
    adjMatrix [][]int // Weighted adjacency matrix
}

func NewDijkstraGraph(vertices int) *DijkstraGraph {
    matrix := make([][]int, vertices)
    for i := range matrix {
        matrix[i] = make([]int, vertices)
        for j := range matrix[i] {
            matrix[i][j] = math.MaxInt32 // Infinity
        }
    }

    return &DijkstraGraph{
        vertices:  vertices,
        adjMatrix: matrix,
    }
}

func (dg *DijkstraGraph) AddEdge(from, to, weight int) {
    dg.adjMatrix[from][to] = weight
    // For undirected graph
    dg.adjMatrix[to][from] = weight
}

func (dg *DijkstraGraph) Dijkstra(start int) ([]int, []int) {
    distances := make([]int, dg.vertices) // Shortest distance from start
    visited := make([]bool, dg.vertices)
    previous := make([]int, dg.vertices) // Previous vertex in path

    // Initialize
    for i := range distances {
        distances[i] = math.MaxInt32
        previous[i] = -1
    }
    distances[start] = 0

    for i := 0; i < dg.vertices-1; i++ {
        // Find unvisited vertex with minimum distance
        minDist := math.MaxInt32
        minVertex := -1

        for v := 0; v < dg.vertices; v++ {
            if !visited[v] && distances[v] < minDist {
                minDist = distances[v]
                minVertex = v
            }
        }

        if minVertex == -1 {
            break // No more reachable vertices
        }

        visited[minVertex] = true

        // Update distances of neighbors
        for v := 0; v < dg.vertices; v++ {
            if !visited[v] && dg.adjMatrix[minVertex][v] != math.MaxInt32 {
                newDist := distances[minVertex] + dg.adjMatrix[minVertex][v]
                if newDist < distances[v] {
                    distances[v] = newDist
                    previous[v] = minVertex
                }
            }
        }
    }

    return distances, previous
}

func (dg *DijkstraGraph) GetPath(previous []int, end int) []int {
    path := []int{}
    current := end

    for current != -1 {
        path = append([]int{current}, path...)
        current = previous[current]
    }

    return path
}

func main() {
    // City navigation example
    cities := NewDijkstraGraph(5) // 5 cities

    // Add roads with travel times (minutes)
    cities.AddEdge(0, 1, 10) // City 0 to 1: 10 min
    cities.AddEdge(0, 3, 5)  // City 0 to 3: 5 min
    cities.AddEdge(1, 2, 1)  // City 1 to 2: 1 min
    cities.AddEdge(1, 3, 2)  // City 1 to 3: 2 min
    cities.AddEdge(2, 4, 4)  // City 2 to 4: 4 min
    cities.AddEdge(3, 1, 3)  // City 3 to 1: 3 min
    cities.AddEdge(3, 2, 9)  // City 3 to 2: 9 min
    cities.AddEdge(3, 4, 2)  // City 3 to 4: 2 min
    cities.AddEdge(4, 0, 7)  // City 4 to 0: 7 min

    distances, previous := cities.Dijkstra(0)

    fmt.Println("Shortest times from city 0:")
    for i, dist := range distances {
        if dist == math.MaxInt32 {
            fmt.Printf("City %d: unreachable\n", i)
        } else {
            fmt.Printf("City %d: %d minutes\n", i, dist)
        }
    }

    // Get path to city 4
    path := cities.GetPath(previous, 4)
    fmt.Printf("Path to city 4: %v (total: %d minutes)\n", path, distances[4])
}

How Dijkstra’s Works:

1. Start with distance 0 to start vertex, infinity to others
2. Find closest unvisited vertex
3. Update distances to its neighbors
4. Repeat until all vertices visited
5. Reconstruct path using previous vertex pointers

Minimum Spanning Trees: Connecting Everything Efficiently 🌉

Kruskal’s Algorithm: Building Road Networks 🛣️

Imagine you need to connect several cities with roads, but you want to use the minimum amount of road possible. That’s a Minimum Spanning Tree (MST)!

package main

import (
    "fmt"
    "sort"
)

// Edge for Kruskal's algorithm
type Edge struct {
    From, To, Weight int
}

// Union-Find structure for cycle detection
type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(size int) *UnionFind {
    parent := make([]int, size)
    rank := make([]int, size)
    for i := range parent {
        parent[i] = i
    }
    return &UnionFind{parent: parent, rank: rank}
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x]) // Path compression
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rootX := uf.Find(x)
    rootY := uf.Find(y)

    if rootX != rootY {
        // Union by rank
        if uf.rank[rootX] < uf.rank[rootY] {
            uf.parent[rootX] = rootY
        } else if uf.rank[rootX] > uf.rank[rootY] {
            uf.parent[rootY] = rootX
        } else {
            uf.parent[rootY] = rootX
            uf.rank[rootX]++
        }
    }
}

func KruskalMST(edges []Edge, vertices int) []Edge {
    // Sort edges by weight
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].Weight < edges[j].Weight
    })

    uf := NewUnionFind(vertices)
    mst := []Edge{}

    for _, edge := range edges {
        if uf.Find(edge.From) != uf.Find(edge.To) {
            uf.Union(edge.From, edge.To)
            mst = append(mst, edge)
        }
    }

    return mst
}

func main() {
    // Power grid connection example
    edges := []Edge{
        {0, 1, 4},  // Town 0-1: $4M to connect
        {0, 7, 8},  // Town 0-7: $8M
        {1, 2, 8},  // Town 1-2: $8M
        {1, 7, 11}, // Town 1-7: $11M
        {2, 3, 7},  // Town 2-3: $7M
        {2, 5, 4},  // Town 2-5: $4M
        {2, 8, 2},  // Town 2-8: $2M
        {3, 4, 9},  // Town 3-4: $9M
        {3, 5, 14}, // Town 3-5: $14M
        {4, 5, 10}, // Town 4-5: $10M
        {5, 6, 2},  // Town 5-6: $2M
        {6, 7, 1},  // Town 6-7: $1M
        {6, 8, 6},  // Town 6-8: $6M
        {7, 8, 7},  // Town 7-8: $7M
    }

    mst := KruskalMST(edges, 9)

    fmt.Println("Minimum Spanning Tree connections:")
    totalCost := 0
    for _, edge := range mst {
        fmt.Printf("Town %d --(%dM$)--> Town %d\n", edge.From, edge.Weight, edge.To)
        totalCost += edge.Weight
    }
    fmt.Printf("Total cost: $%dM\n", totalCost)
}

Kruskal’s Algorithm Steps:

1. Sort all edges by weight (cheapest first)
2. Add edges one by one if they don’t create cycles
3. Use Union-Find to detect cycles efficiently
4. Result connects all vertices with minimum total weight

Real-World Applications 🌍

1. Social Network Friend Suggestions 💡

func SuggestFriends(graph *Graph, user int) []int {
    visited := make([]bool, graph.vertices)
    suggestions := make(map[int]int) // Person -> mutual friends count

    // BFS to find friends of friends
    queue := []int{user}
    visited[user] = true
    distance := make([]int, graph.vertices)
    distance[user] = 0

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        for _, friend := range graph.adjList[current] {
            if !visited[friend] {
                visited[friend] = true
                distance[friend] = distance[current] + 1
                queue = append(queue, friend)

                // Only suggest 2nd degree connections
                if distance[friend] == 2 {
                    suggestions[friend]++
                }
            }
        }
    }

    // Sort by mutual friends count
    type suggestion struct {
        person, mutualFriends int
    }

    var sorted []suggestion
    for person, count := range suggestions {
        sorted = append(sorted, suggestion{person, count})
    }

    sort.Slice(sorted, func(i, j int) bool {
        return sorted[i].mutualFriends > sorted[j].mutualFriends
    })

    result := make([]int, len(sorted))
    for i, s := range sorted {
        result[i] = s.person
    }

    return result
}

2. Course Prerequisites Checker 📚

func CanFinishCourses(numCourses int, prerequisites [][]int) bool {
    // Build graph: course -> list of courses that depend on it
    graph := make([][]int, numCourses)
    inDegree := make([]int, numCourses) // Number of prerequisites for each course

    for _, prereq := range prerequisites {
        course := prereq[0]
        prereqCourse := prereq[1]
        graph[prereqCourse] = append(graph[prereqCourse], course)
        inDegree[course]++
    }

    // Find courses with no prerequisites
    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    completed := 0
    for len(queue) > 0 {
        currentCourse := queue[0]
        queue = queue[1:]
        completed++

        // Reduce prerequisites for dependent courses
        for _, dependent := range graph[currentCourse] {
            inDegree[dependent]--
            if inDegree[dependent] == 0 {
                queue = append(queue, dependent)
            }
        }
    }

    return completed == numCourses
}

func main() {
    // Course prerequisites: [course, prerequisite]
    prereqs := [][]int{
        {1, 0}, // Course 1 requires course 0
        {2, 0}, // Course 2 requires course 0
        {3, 1}, // Course 3 requires course 1
        {3, 2}, // Course 3 requires course 2
    }

    canFinish := CanFinishCourses(4, prereqs)
    fmt.Println("Can finish all courses?", canFinish) // true
}

3. Network Routing: Finding Best Paths 📡

func FindBestRoute(network *DijkstraGraph, from, to int, criteria string) []int {
    // Different criteria: "fastest", "cheapest", "most_reliable"
    distances, previous := network.Dijkstra(from)

    if distances[to] == math.MaxInt32 {
        return nil // No route found
    }

    // Reconstruct path
    path := []int{}
    current := to
    for current != -1 {
        path = append([]int{current}, path...)
        current = previous[current]
    }

    return path
}

Graph Algorithm Cheat Sheet 📋

Practice Problems 🎯

1. Flight Route Optimizer: Find cheapest flight route between cities
2. Zombie Infection: Model how a virus spreads through a social network
3. Power Grid: Connect cities with minimum power line cost
4. Recipe Dependencies: Order cooking steps for complex recipes
5. Traffic Light Timing: Optimize traffic light sequences
6. Computer Network: Find most reliable data path

Congratulations! 🎉

You’ve mastered graph algorithms! From basic concepts to advanced applications, you now understand how graphs power:

• GPS Navigation (shortest paths)
• Social Networks (connections, suggestions)
• Network Routing (efficient data flow)
• Course Planning (prerequisites)
• Transportation (route optimization)
• Computer Networks (efficient connections)

Graphs are everywhere in programming. Keep practicing, and soon you’ll see graph problems in every application you build! 🚀

Next Steps:

• Implement these algorithms in your own projects
• Study more advanced graph algorithms (A*, Bellman-Ford)
• Explore graph databases and real-world applications
• Build your own social network or navigation app!