Advanced Graph Algorithms

Introduction

In this chapter, we explore some of the most powerful algorithms used in graphs. These algorithms allow us to solve problems like:

• Finding the shortest path between nodes

• Finding the minimum spanning tree

• Detecting negative cycles

• Finding all-pairs shortest paths

These algorithms are widely used in real-world systems such as:

• Google Maps

• Network routing

• Recommendation engines

• Traffic optimization

• Telecommunication systems

1. Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights.

Use Cases

• Navigation systems

• Network routing

• Robot path planning

How It Works

1. Start at the source node

2. Pick the node with the smallest distance

3. Update distances of its neighbors

4. Repeat until all nodes are processed

C# Implementation

int[] Dijkstra(List<(int to, int weight)>[] graph, int source)
{
    int n = graph.Length;
    int[] dist = Enumerable.Repeat(int.MaxValue, n).ToArray();
    dist[source] = 0;

    PriorityQueue<int, int> pq = new();
    pq.Enqueue(source, 0);

    while (pq.Count > 0)
    {
        int node = pq.Dequeue();

        foreach (var edge in graph[node])
        {
            int next = edge.to;
            int weight = edge.weight;

            if (dist[node] + weight < dist[next])
            {
                dist[next] = dist[node] + weight;
                pq.Enqueue(next, dist[next]);
            }
        }
    }

    return dist;
}

Time Complexity

• Using priority queue: O((V + E) log V)

2. Bellman-Ford Algorithm

Bellman-Ford is used to find the shortest paths even when negative weights exist.

Why Use Bellman-Ford?

Dijkstra fails when negative weights are present.

Bellman-Ford:

• Handles negative weights

• Detects negative cycles

How It Works

Repeat V-1 times:

• Relax all edges

Then check for negative cycles.

C# Implementation

int[] BellmanFord(int n, List<(int u, int v, int w)> edges, int source)
{
    int[] dist = Enumerable.Repeat(int.MaxValue, n).ToArray();
    dist[source] = 0;

    for (int i = 0; i < n - 1; i++)
    {
        foreach (var (u, v, w) in edges)
        {
            if (dist[u] != int.MaxValue && dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
            }
        }
    }

    return dist;
}

Time Complexity

• O(V × E) — slower than Dijkstra

3. Floyd–Warshall Algorithm

This algorithm finds the shortest paths between all pairs of nodes.

Use Cases

• Traffic systems

• Routing algorithms

• Distance matrix generation

How It Works

Dynamic Programming approach:

dist[i][j] = minimum distance from i to j

Update using intermediate nodes.

C# Implementation

int[,] FloydWarshall(int[,] dist, int n)
{
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (dist[i, k] + dist[k, j] < dist[i, j])
                {
                    dist[i, j] = dist[i, k] + dist[k, j];
                }
            }
        }
    }
    return dist;
}

Time Complexity

• O(n³)

4. Minimum Spanning Tree (MST)

A Minimum Spanning Tree connects all nodes using the minimum possible total edge weight.

Two major algorithms:

• Kruskal’s Algorithm

• Prim’s Algorithm

Kruskal’s Algorithm

Kruskal builds the MST by selecting the smallest edges first, ensuring no cycles are formed.

Steps

1. Sort edges by weight

2. Add smallest edge that doesn't form a cycle

3. Use Disjoint Set (Union-Find) for cycle detection

C# Implementation (Simplified)

int Kruskal(int n, List<(int u, int v, int w)> edges)
{
    edges.Sort((a, b) => a.w.CompareTo(b.w));
    int total = 0;

    int[] parent = Enumerable.Range(0, n).ToArray();

    int Find(int x)
    {
        if (parent[x] == x) return x;
        return parent[x] = Find(parent[x]);
    }

    void Union(int a, int b)
    {
        parent[Find(a)] = Find(b);
    }

    foreach (var (u, v, w) in edges)
    {
        if (Find(u) != Find(v))
        {
            Union(u, v);
            total += w;
        }
    }

    return total;
}

Time Complexity

• Sorting edges: O(E log E)

• Union-Find operations: almost O(1)

Prim’s Algorithm

Prim builds the MST by expanding from the starting node, always choosing the smallest edge available.

Use Cases

• Dense graphs

• Network cable routing

C# Implementation

int Prim(List<(int to, int weight)>[] graph)
{
    int n = graph.Length;
    bool[] visited = new bool[n];
    PriorityQueue<(int node, int weight), int> pq = new();
    pq.Enqueue((0, 0), 0);

    int total = 0;

    while (pq.Count > 0)
    {
        var (node, weight) = pq.Dequeue();
        if (visited[node]) continue;

        visited[node] = true;
        total += weight;

        foreach (var edge in graph[node])
        {
            if (!visited[edge.to])
            {
                pq.Enqueue((edge.to, edge.weight), edge.weight);
            }
        }
    }

    return total;
}

Time Complexity

• O((V + E) log V) using priority queue

Summary

Advanced graph algorithms solve critical real-world problems involving optimization, shortest paths, and cost minimization.

Key Takeaways

• Dijkstra ? shortest paths (no negative weights)

• Bellman–Ford ? handles negative weights + detects cycles

• Floyd–Warshall ? all-pairs shortest paths

• Kruskal ? MST using edge sorting

• Prim ? MST using greedy expansion

These algorithms are essential for interviews and system-level applications.