El tutorial o código que verás en este post es la resolución más sencilla y efectiva que encontramos a esta inquietud o dilema.
Solución:
El algoritmo que ha sugerido encontrará el camino más corto en este gráfico, pero no en todos los gráficos en general. Por ejemplo, considere este gráfico:
Rastreemos la ejecución de su algoritmo.
- Primero, estableces d(A) a 0 y las demás distancias a ∞.
- Luego expande el nodo Aestableciendo d(B) a 1, d(C) a 0, y d(D) a 99.
- A continuación, se expande Csin cambios netos.
- Luego te expandes Bque no tiene ningún efecto.
- Finalmente, expandes Dque cambia d(B) a -201.
Note que al final de esto, sin embargo, que d(C) sigue siendo 0, aunque el camino más corto a C tiene longitud -200. Esto significa que su algoritmo no calcula las distancias correctas a todos los nodos. Además, incluso si tuviera que almacenar punteros retrospectivos que indiquen cómo llegar de cada nodo al nodo de inicio Aterminarías tomando el camino equivocado de regreso C a A.
La razón de esto es que el algoritmo de Dijkstra (y su algoritmo) son algoritmos codiciosos que asumen que una vez que han calculado la distancia a algún nodo, la distancia encontrada debe ser la distancia óptima. En otras palabras, el algoritmo no se permite tomar la distancia de un nodo que ha expandido y cambiar cuál es esa distancia. En el caso de los bordes negativos, su algoritmo y el algoritmo de Dijkstra pueden “sorprenderse” al ver un borde de costo negativo que de hecho disminuiría el costo de la mejor ruta desde el nodo inicial a algún otro nodo.
¡Espero que esto ayude!
Tenga en cuenta que Dijkstra funciona incluso para pesos negativos, si el Gráfico no tiene ciclos negativos, es decir, ciclos cuyo peso total es menor que cero.
Por supuesto, uno podría preguntarse, ¿por qué en el ejemplo hecho por templatetypedef Dijkstra falla a pesar de que no hay ciclos negativos, de hecho ni siquiera ciclos. Esto se debe a que está usando otro criterio de parada, que mantiene el algoritmo tan pronto como se alcanza el nodo de destino (o todos los nodos se han liquidado una vez, no lo especificó exactamente). En un gráfico sin pesos negativos esto funciona bien.
Si se utiliza el criterio de parada alternativo, que detiene el algoritmo cuando la cola de prioridad (montón) se queda vacía (este criterio de parada también se utilizó en la pregunta), entonces dijkstra encontrará la distancia correcta incluso para gráficos con pesos negativos pero sin ciclos negativos.
Sin embargo, en este caso, se pierde el límite de tiempo asintótico de dijkstra para gráficos sin ciclos negativos. Esto se debe a que un nodo previamente asentado se puede reinsertar en el montón cuando se encuentra una mejor distancia debido a los pesos negativos. Esta propiedad se denomina corrección de etiquetas.
no usó S en ninguna parte de su algoritmo (además de modificarlo). la idea de dijkstra es que una vez que un vértice está en S, no se modificará nunca más. en este caso, una vez que B esté dentro de S, no volverás a alcanzarlo por C.
este hecho asegura la complejidad de O(E+VlogV) [otherwise, you will repeat edges more then once, and vertices more then once]
en otras palabras, es posible que el algoritmo que publicaste no esté en O (E + VlogV), como prometió el algoritmo de dijkstra.
Reseñas y puntuaciones del tutorial
Si guardas algún recelo y forma de ascender nuestro crónica puedes ejecutar una aclaración y con placer lo analizaremos.