¿Qué es el Algoritmo de Dijkstra?

El algoritmo de Dijkstra es una técnica ampliamente utilizada para encontrar el camino más corto entre un nodo de origen y todos los demás nodos en un grafo ponderado no dirigido. Utiliza una estructura de cola de prioridad para garantizar la eficiencia durante la búsqueda.

El Código

                
class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }

  dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = []; // to return at end
    let smallest;

    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }

    while (nodes.values.length) {
      smallest = nodes.dequeue().val;
      if (smallest === finish) {
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjacencyList[smallest]) {
          let nextNode = this.adjacencyList[smallest][neighbor];
          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;
          if (candidate < distances[nextNeighbor]) {
            distances[nextNeighbor] = candidate;
            previous[nextNeighbor] = smallest;
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    return path.concat(smallest).reverse();
  }
}

// Ejemplo de uso
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");

graph.addEdge("A", "B", 4);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "E", 3);
graph.addEdge("C", "D", 2);
graph.addEdge("C", "F", 4);
graph.addEdge("D", "E", 3);
graph.addEdge("D", "F", 1);
graph.addEdge("E", "F", 1);

console.log("Camino más corto de A a E:", graph.dijkstra("A", "E"));
                
            

Puntos Clave del Algoritmo

• Entrada: Un grafo ponderado, un nodo inicial y un nodo final.
• Salida: El camino más corto desde el nodo inicial hasta el nodo final.
• Método:
  • Utiliza una cola de prioridad para priorizar los nodos con menor distancia acumulada.
  • Actualiza las distancias desde el nodo actual a sus vecinos.
  • Registra el nodo previo para reconstruir el camino más corto.
• Complejidad:
  • Tiempo: O(V + E log V), donde V es el número de vértices y E el número de aristas.
  • Espacio: O(V + E) para almacenar el grafo y la cola de prioridad.
• Ventajas: Encuentra caminos más cortos en grafos ponderados de manera eficiente.
• Desventajas: No funciona correctamente con aristas de peso negativo (usar Bellman-Ford en ese caso).

Ejemplo de Ejecución

Grafo inicial:

• Vértices: A, B, C, D, E, F
• Aristas: A-B(4), A-C(2), B-E(3), C-D(2), C-F(4), D-E(3), D-F(1), E-F(1)

Camino más corto desde A hasta E:

1. Inicio en A, distancias: { A: 0, B: ∞, C: ∞, D: ∞, E: ∞, F: ∞ }.
2. Selecciona C (menor distancia acumulada) y actualiza las distancias de sus vecinos.
3. Continúa visitando los nodos según la prioridad en la cola.
4. Al llegar a E, reconstruye el camino: [A, C, D, E].

Resultado final: Camino más corto es [A, C, D, E] con distancia total de 7.

Información Adicional

El algoritmo de Dijkstra es esencial en redes, sistemas de navegación y análisis de rutas. Su implementación con una cola de prioridad lo hace eficiente para aplicaciones en grafos densos y es fundamental en algoritmos de optimización.