Advanced Graphs

Reach for it when

• Edge weights or costs (network delay, cheapest flights)
• Connect all points at minimum total cost
• Use every edge exactly once (itinerary)

Core idea

Dijkstra pops the closest unsettled node from a min-heap and relaxes its edges; it needs non-negative weights. Bellman-Ford relaxes all edges k times and handles 'at most k stops'. Prim and Kruskal build a minimum spanning tree by always taking the cheapest edge that does not form a cycle.

Template · O(E log V) time, O(V + E) space

import heapq

def dijkstra(graph, src):          # graph[u] = [(v, w), ...]
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                 # stale entry
        for v, w in graph[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist

vector<long long> dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
    vector<long long> dist(graph.size(), LLONG_MAX);  // graph[u] = {(v, w), ...}
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> heap;
    dist[src] = 0;
    heap.push({0, src});
    while (!heap.empty()) {
        auto [d, u] = heap.top(); heap.pop();
        if (d > dist[u]) continue;                     // stale entry
        for (auto [v, w] : graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push({dist[v], v});
            }
        }
    }
    return dist;
}

Common pitfalls

• Dijkstra breaks with negative edges
• Skip stale heap entries instead of decrease-key
• With a stop limit, copy the distance array per round (Bellman-Ford)

Practice · 0 / 6 done

• Cheapest Flights Within K StopsMedium
• Min Cost to Connect All PointsMedium
• Network Delay TimeMedium
• Alien DictionaryHard
• Reconstruct ItineraryHard
• Swim In Rising WaterHard