El grafo dirigido de las diapositivas, ejecutándose. Cada paso dice qué arista se está relajando y por qué una distancia mejora o no, y la tabla de la derecha se llena igual que en clase.
El grafo
distancia provisional pivote de este paso distancia ya definitiva
Paso 0
Pulsa Ejecutar y el algoritmo avanza solo. O ve paso a paso con Siguiente.
Tabla de iteraciones
La fila de cada iteración aparece cuando se elige su pivote.
Aquí Dijkstra se equivoca. Fíjate en qué pasa con B: se da por definitivo con coste 2 y no se vuelve a mirar. Después, desde C, aparece un camino de coste 1 que ya no se puede aprovechar, porque Dijkstra nunca reabre un nodo cerrado. Esa es la razón de la condición: con pesos no negativos, el nodo más cercano no visitado no puede mejorar por ningún camino posterior. Con una arista negativa, sí. Para esos grafos está Bellman-Ford.