Algoritmo de Dijkstra

¿Qué es el Algoritmo de Floyd-Warshall?

El Algoritmo de Floyd-Warshall es un método dinámico para encontrar las distancias más cortas entre todos los pares de vértices en un grafo ponderado. Es especialmente útil para grafos densos y puede manejar aristas de peso negativo, siempre que no existan ciclos negativos.

El Código

                
function floydWarshall(graph) {
  const dist = [];
  const V = graph.length;

  // Inicializar la matriz de distancias con los valores del grafo
  for (let i = 0; i < V; i++) {
    dist[i] = [];
    for (let j = 0; j < V; j++) {
      if (i === j) {
        dist[i][j] = 0;
      } else if (graph[i][j] !== 0) {
        dist[i][j] = graph[i][j];
      } else {
        dist[i][j] = Infinity;
      }
    }
  }

  // Aplicar el algoritmo de Floyd-Warshall
  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

// Ejemplo de uso
const graph = [
  [0, 3, Infinity, 5],
  [2, 0, Infinity, 4],
  [Infinity, 1, 0, Infinity],
  [Infinity, Infinity, 2, 0],
];

console.log("Matriz de distancias más cortas:");
console.table(floydWarshall(graph));

Puntos Clave del Algoritmo

  • Entrada: Un grafo ponderado representado como una matriz de adyacencia.
  • Salida: Una matriz de distancias donde cada entrada dist[i][j] contiene la distancia más corta entre el vértice i y j.
  • Método:
    • Inicializa una matriz de distancias con los valores del grafo, estableciendo Infinity para aristas no existentes.
    • Itera sobre todos los vértices posibles como nodos intermedios para actualizar las distancias.
    • Si se encuentra un camino más corto pasando por un nodo intermedio, actualiza la distancia.
  • Complejidad:
    • Tiempo: O(V³), donde V es el número de vértices en el grafo.
    • Espacio: O(V²) debido al almacenamiento de la matriz de distancias.
  • Ventajas: Encuentra distancias más cortas entre todos los pares de nodos en un solo paso.
  • Desventajas: No es eficiente para grafos grandes y dispersos debido a su complejidad cúbica.

Ejemplo de Ejecución

Matriz de entrada:

                
[
  [0, 3, Infinity, 5],
  [2, 0, Infinity, 4],
  [Infinity, 1, 0, Infinity],
  [Infinity, Infinity, 2, 0],
]

Proceso del algoritmo:

  1. Inicializa la matriz de distancias según los valores del grafo.
  2. Itera considerando cada vértice como un nodo intermedio.
  3. Actualiza las distancias más cortas utilizando el nodo intermedio cuando sea posible.

Matriz de salida (distancias más cortas):

                
[
  [0, 3, 7, 5],
  [2, 0, 6, 4],
  [Infinity, 1, 0, 3],
  [Infinity, Infinity, 2, 0],
]

Información Adicional

El algoritmo de Floyd-Warshall es ideal para problemas donde es necesario calcular distancias entre todos los pares de nodos, como en redes de transporte o análisis de caminos en grafos densos. Sin embargo, su alto costo computacional lo hace menos adecuado para grafos dispersos grandes.

Whatsapp Mentores Tech