Lesson 3 · Problem-solving methods

Advanced Graph Algorithms

While BFS and DFS allow you to traverse graphs, advanced algorithms are needed to solve optimization problems on weighted graphs or dependency problems on directed acyclic graphs.

Dijkstra's Algorithm

Used to find the shortest path from a single source node to all other nodes in a graph with non-negative edge weights.

It greedily selects the unvisited node with the smallest known distance from the source using a Priority Queue, and then relaxes (updates) the distances to its neighbors.

Requires non-negative weights
Uses a Min-Heap
O((V + E) log V) complexity

Bellman-Ford Algorithm

Also finds shortest paths, but handles negative edge weights. It works by relaxing all edges V-1 times (where V is the number of vertices).

For a single-source run, an edge that still relaxes on the V-th pass reveals a negative cycle reachable from that source. Detecting a negative cycle anywhere requires a super-source or initially setting every distance to zero.

Handles negative weights
Detects source-reachable negative cycles
Slower: O(V * E) complexity

Key reference

Terms, operations, and practical uses

Algorithms

Dijkstra'sFinds the shortest path from a starting node to all other nodes. Only works with non-negative edge weights.
Bellman-FordFinds shortest paths and can handle negative edge weights. Can also detect negative weight cycles.
Kruskal's / Prim'sAlgorithms to find the Minimum Spanning Tree (MST) of a weighted graph.

Key concepts

Edge RelaxationThe process of updating the shortest known distance to a node if a shorter path is found via a neighboring node.
Topological SortA linear ordering of vertices in a Directed Acyclic Graph (DAG) such that every directed edge U -> V means U comes before V.
DAGDirected Acyclic Graph. A directed graph with no cycles, a requirement for Topological Sort and DP on graphs.

Data structures used

Min-HeapUsed in Dijkstra's and Prim's algorithms to efficiently extract the next closest node or smallest edge.
Disjoint SetUsed in Kruskal's algorithm to efficiently check if adding an edge will create a cycle.
In-Degree ArrayUsed in Kahn's Algorithm for Topological Sort to track how many prerequisites a node has left.

Code example

Kahn's Algorithm for Topological Sort

from collections import deque

def topological_sort(n, edges):
    in_degree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []
# A=0, B=1, C=2 with edges A->C and B->C
names = ['A', 'B', 'C']
order = topological_sort(3, [(0, 2), (1, 2)])
print('Order: [' + ', '.join(names[i] for i in order) + ']')

vector<int> topologicalSort(int n, vector<pair<int,int>>& edges) {
    vector<int> inDegree(n, 0);
    vector<vector<int>> graph(n);
    for (auto& edge : edges) {
        graph[edge.first].push_back(edge.second);
        inDegree[edge.second]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int neighbor : graph[node]) {
            if (--inDegree[neighbor] == 0) q.push(neighbor);
        }
    }
    return order;
}

static List<Integer> topologicalSort(int n, int[][] edges) {
    int[] inDegree = new int[n];
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) if (inDegree[i] == 0) queue.add(i);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int neighbor : graph.get(node)) {
            if (--inDegree[neighbor] == 0) queue.add(neighbor);
        }
    }
    return order;
}

InputDAG: A->C, B->C

OutputOrder: [A, B, C]

Example

Run the example step by step

Output

Minimum Spanning Trees

An MST connects every vertex of a connected, weighted, undirected graph without cycles and with minimum total edge weight. On a disconnected graph, the corresponding result is a minimum spanning forest.

Kruskal's algorithm builds it by sorting all edges and adding them greedily using a Disjoint Set to avoid cycles. Prim's algorithm builds it by growing a single tree outward from a starting node using a Priority Queue.

Kruskal's: uses Disjoint Sets
Prim's: uses Priority Queue
Requires an undirected graph

Topological Sort

Applicable only to Directed Acyclic Graphs (DAGs). It linearly orders vertices such that for every directed edge U -> V, vertex U comes before V.

It is the standard algorithm for resolving dependencies, such as scheduling tasks with prerequisites or resolving package dependencies in a build system. Can be implemented with DFS or Kahn's Algorithm (BFS with in-degrees).

Only works on DAGs
Resolves prerequisites/dependencies
O(V + E) complexity