Algoritmos avanzados de grafos

Algoritmos avanzados de grafos

Estos algoritmos resuelven problemas complejos como caminos mínimos y árboles de expansión mínima.

Algoritmo de Dijkstra (camino más corto)

Encuentra el camino más corto desde el origen a todos los vértices. No funciona con pesos negativos.

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 (maneja pesos negativos)

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 (caminos mínimos para todos los pares)

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];
        }
      }
    }

  

    
Aprende más
    

      
        
Algoritmo de Dijkstra
        
Explicación detallada de caminos mínimos en grafos.
      
      
        
CP-Algorithms: Dijkstra
        
Perspectiva de programación competitiva sobre Dijkstra.
      
    
  

  }
  
  return dist;
}

// Time: O(V³)

Kruskal MST (árbol de expansión mínima)

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)