Advanced Graph Algorithms

Advanced Graph Algorithms

These algorithms solve complex graph problems like shortest paths and minimum spanning trees.

Dijkstra's Algorithm (Shortest Path)

Finds shortest path from source to all vertices. Doesn't work with negative weights.

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  const pq = [[0, start]]; // [distance, node]
  
  // Initialize distances
  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[start] = 0;
  
  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [currentDist, currentNode] = pq.shift();
    
    if (visited.has(currentNode)) continue;
    visited.add(currentNode);
    
    for (const [neighbor, weight] of graph[currentNode]) {
      const distance = currentDist + weight;
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        pq.push([distance, neighbor]);
      }
    }
  }
  
  return distances;
}

// Time: O((V + E) log V) with priority queue

Bellman-Ford (Handles Negative Weights)

function bellmanFord(graph, start, V) {
  const distances = Array(V).fill(Infinity);
  distances[start] = 0;
  
  // Relax edges V-1 times
  for (let i = 0; i < V - 1; i++) {
    for (const [u, v, weight] of graph) {
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
      }
    }
  }
  
  // Check for negative cycles
  for (const [u, v, weight] of graph) {
    if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
      return "Negative cycle detected";
    }
  }
  
  return distances;
}

// Time: O(VE)

Floyd-Warshall (All Pairs Shortest Path)

function floydWarshall(graph) {
  const V = graph.length;
  const dist = graph.map(row => [...row]);
  
  // Try all intermediate vertices
  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }

  

    
Learn More
    

      
        
Dijkstra's Algorithm
        
In-depth explanation of finding shortest paths in graphs.
      
      
        
CP-Algorithms: Dijkstra
        
Competitive programming perspective on Dijkstra's algorithm.
      
    
  

  }
  
  return dist;
}

// Time: O(V³)

Kruskal's MST (Minimum Spanning Tree)

function kruskalMST(edges, V) {
  edges.sort((a, b) => a[2] - b[2]); // Sort by weight
  const parent = Array.from({ length: V }, (_, i) => i);
  
  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }
  
  function union(x, y) {
    parent[find(x)] = find(y);
  }
  
  const mst = [];
  for (const [u, v, weight] of edges) {
    if (find(u) !== find(v)) {
      union(u, v);
      mst.push([u, v, weight]);
    }
  }
  
  return mst;
}

// Time: O(E log E)