🌇DSA
← Back
AlgorithmAdvanced
🛸

Advanced Graph Algorithms

Shortest paths and connectivity

⏱️ 8–15 hours🧩 10 LeetCode
🔒 Login to unlock solutions and track progress. Login

What is it?

Advanced graph algorithms solve problems that basic BFS/DFS cannot — like finding the cheapest route, detecting negative cost cycles, or connecting nodes with minimum cable.

Core Algorithms

| Algorithm | Solves | Complexity | |------------------|--------------------------------------|----------------| | Dijkstra | Shortest path (all weights ≥ 0) | O((V+E) log V) | | Bellman-Ford | Shortest path (negative weights ok) | O(V × E) | | Floyd-Warshall | All-pairs shortest paths | O(V³) | | Union-Find | Are two nodes connected? | O(α(n)) ≈ O(1) | | Topological Sort | Task ordering in a dependency graph | O(V + E) | | Kruskal / Prim | Minimum Spanning Tree | O(E log E) |

Real-World Examples

GPS route (Dijkstra)
Network routing (Bellman-Ford)
Flight prices all-pairs (Floyd)
Friend groups (Union-Find)
Build order (Topo Sort)
Broadband cable layout (MST)

Code Example

What this code shows

Dijkstra from node A on a weighted graph. Each step picks the unvisited node with the smallest known distance, then relaxes its neighbours. Result: the shortest distance from A to every other node.

function dijkstra(graph, src) {
// initialise all distances to infinity
const dist = Object.fromEntries(Object.keys(graph).map(n => [n, Infinity]));
dist[src] = 0; // distance to source is 0

const visited = new Set();

while (visited.size < Object.keys(graph).length) {
  // pick the unvisited node with the smallest distance
  const u = Object.keys(dist)
    .filter(n => !visited.has(n))
    .reduce((a, b) => dist[a] < dist[b] ? a : b);
  visited.add(u);

  // relax each neighbour: update if we found a shorter path
  for (const [v, weight] of graph[u]) {
    if (dist[u] + weight < dist[v]) {
      dist[v] = dist[u] + weight;
    }
  }
}
return dist;
}

// graph edges: [neighbour, weight]
const g = {
A: [["B",1],["C",4]], // A→B costs 1, A→C costs 4
B: [["C",2],["D",5]], // B→C costs 2, B→D costs 5
C: [["D",1]],         // C→D costs 1
D: []
};
console.log(dijkstra(g, "A"));
// { A:0, B:1, C:3, D:4 }

Expected Output

Distances from A:
A → 0
B → 1
C → 3
D → 4

LeetCode Practice