La parte crucial del algoritmo de Dijkstra es que en la iteración del algoritmo encontramos el i- ésimo nodo más cercano al nodo desde el que estamos buscando. El primer nodo más cercano al nodo fuente es en realidad el que tiene un peso de borde mínimo entre él y la fuente. Esto es bastante intuitivo. Ahora piense en el segundo vértice más cercano. Parece ser otro vecino del nodo inicial o algún nodo vecino del primer nodo más cercano. Y así sucesivamente y así sucesivamente. Pero, ¿qué pasa si el borde desde el primer vértice más cercano a algunos de sus vecinos es negativo? Significa que el nodo al que está conectado está más cerca de la fuente que el nodo que ya marcamos como el primero más cercano, lo que definitivamente es un absurdo.
En la práctica, para comprender por qué no funciona, imagine un gráfico en forma de diamante compuesto por los cuatro nodos y suponga que todos los bordes tienen una longitud positiva además de uno ( 1 – (5) -> 2 , 1 – (7) -> 3 , 2 – (1) -> 4 , 3 – (-6) -> 4 ). Supongamos que queremos encontrar la distancia más corta de 1 a 4 . El algoritmo seguiría los siguientes pasos:
- Init: empuja el nodo de origen 1 a la cola de prioridad.
- Salga de la cola ya que es el único, márquelo como el 0 más cercano a sí mismo. Ahora empuje a los vecinos 2 y 3 a la cola.
- Pop un vértice 2 de la cola ya que tiene una distancia menor a 1 que 3 . Márquelo como el más cercano a la fuente con una distancia igual a 5. Empuje a su vecino solitario 4 a la cola guardando la distancia 5 + 1 = 6.
- Ahora tenemos dos nodos en la cola de prioridad: el nodo 3 con la distancia 7 y el nodo 4 con la distancia 6. Obviamente sacaremos el nodo 4 de la cola, ya que parece más cerca del nodo 1 . Lo entendemos, descubrimos que es el nodo al que estábamos buscando la distancia y sugiriendo que es el nodo más cercano en la iteración actual rompiendo el algoritmo totalmente convencido de que encontramos la distancia correcta.
- Definitivamente estamos equivocados porque la verdadera ruta de la distancia más corta de 1 a 4 atraviesa el nodo 3 dando el resultado final para que sea igual a 7-6 = 1.
* Perdón por la falta de fotos. Escrito en un iPad.
- Dadas dos cadenas de longitud N, ¿cómo encuentro la ventana máxima de patrones coincidentes si pueden mutarse?
- Se le da una matriz de números MxN, con la propiedad de que los números aumentan a medida que avanza por cada columna y hacia la derecha en cada fila. ¿Cómo puede verificar eficientemente si un número dado está en la matriz?
- Cómo resolver la pregunta en la descripción a continuación
- ¿Cuál es el mejor algoritmo de eliminación para un árbol de búsqueda binario sin usar un nodo padre adicional?
- ¿Cuál: Estructura de datos y pensamiento algorítmico con Python (Narasimha Karumanchi) o Estructuras de datos y algoritmos en Python (Michael T. Goodrich)?
