Shortest Path Algorithms

Algorithm Steps

1. Initialize distances of all vertices as infinite and distance of the source vertex as 0
2. Create a priority queue and insert all vertices with their distances
3. While the priority queue is not empty:
   • Extract the vertex with the minimum distance
   • For each adjacent vertex, if the distance through the current vertex is shorter than the known distance, update the distance and predecessor

Implementation

function dijkstra(graph, source) {
  const vertices = graph.vertices.length;
  const adj = graph.adjList;
  
  // Initialize distances as infinity
  const dist = Array(vertices).fill(Infinity);
  const prev = Array(vertices).fill(-1);
  
  // Distance to source is 0
  dist[source] = 0;
  
  // Priority queue to store vertices that need to be processed
  const pq = new MinPriorityQueue();
  pq.enqueue(source, 0);
  
  while (!pq.isEmpty()) {
    // Extract vertex with minimum distance
    const { element: u, priority: dist_u } = pq.dequeue();
    
    // If we've found a longer path, skip
    if (dist_u > dist[u]) continue;
    
    // Relax all adjacent vertices
    for (const [v, weight] of adj[u]) {
      const alt = dist[u] + weight;
      
      // If we found a shorter path to v
      if (alt < dist[v]) {
        dist[v] = alt;
        prev[v] = u;
        pq.enqueue(v, alt);
      }
    }
  }
  
  return { dist, prev };
}

// Helper function to reconstruct path
function getPath(prev, target) {
  const path = [];
  let current = target;
  
  while (current !== -1) {
    path.unshift(current);
    current = prev[current];
  }
  
  return path;
}

Algorithm Steps

1. Initialize distances of all vertices as infinite and distance of the source vertex as 0
2. Relax all edges |V| - 1 times (where |V| is the number of vertices):
   • For each edge (u, v) with weight w, if dist(u) + w < dist(v), update dist(v) = dist(u) + w
3. Check for negative weight cycles by attempting one more round of relaxation:
   • If any distance can still be reduced, there's a negative weight cycle

Implementation

function bellmanFord(graph, source) {
  const vertices = graph.vertices.length;
  const edges = graph.edges;
  
  // Initialize distances as infinity
  const dist = Array(vertices).fill(Infinity);
  const prev = Array(vertices).fill(-1);
  
  // Distance to source is 0
  dist[source] = 0;
  
  // Relax all edges |V| - 1 times
  for (let i = 0; i < vertices - 1; i++) {
    for (const edge of edges) {
      const { src: u, dest: v, weight } = edge;
      
      if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        prev[v] = u;
      }
    }
  }
  
  // Check for negative weight cycles
  for (const edge of edges) {
    const { src: u, dest: v, weight } = edge;
    
    if (dist[u] !== Infinity && dist[u] + weight < dist[v]) {
      // Negative weight cycle exists
      return { hasNegativeCycle: true };
    }
  }
  
  return { dist, prev, hasNegativeCycle: false };
}

Algorithm Steps

1. Initialize the distance matrix with direct edge weights (set to infinity if no direct edge exists)
2. For each vertex k as an intermediate vertex:
   • For each pair of vertices (i, j), check if the path through k is shorter than the known direct path
   • If so, update the shortest path: dist[i][j] = dist[i][k] + dist[k][j]

Implementation

function floydWarshall(graph) {
  const vertices = graph.vertices.length;
  
  // Initialize distance matrix
  const dist = Array(vertices).fill().map(() => Array(vertices).fill(Infinity));
  const next = Array(vertices).fill().map(() => Array(vertices).fill(null));
  
  // Set distance to self as 0
  for (let i = 0; i < vertices; i++) {
    dist[i][i] = 0;
  }
  
  // Set direct edge weights and initialize next matrix
  for (const edge of graph.edges) {
    const { src: u, dest: v, weight } = edge;
    dist[u][v] = weight;
    next[u][v] = v;
  }
  
  // Main algorithm
  for (let k = 0; k < vertices; k++) {
    for (let i = 0; i < vertices; i++) {
      for (let j = 0; j < vertices; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity && dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
          next[i][j] = next[i][k];
        }
      }
    }
  }
  
  // Check for negative cycles
  for (let i = 0; i < vertices; i++) {
    if (dist[i][i] < 0) {
      return { hasNegativeCycle: true };
    }
  }
  
  return { dist, next, hasNegativeCycle: false };
}

// Helper function to reconstruct path
function getPath(next, start, end) {
  if (next[start][end] === null) return [];
  
  const path = [start];
  let current = start;
  
  while (current !== end) {
    current = next[current][end];
    path.push(current);
  }
  
  return path;
}