¿El algoritmo de dijkstras relaja los bordes de la ruta más corta en orden?

Question

En el ejercicio "Introducción a los algoritmos, tercera edición" 24.3-5, quiere un ejemplo de que esto está mal (no siempre es cierto). ¿Es eso posible? En mi opinión, esto es imposible porque cada borde está relajado en un momento en que el camino al vértice actual ya está decidido.

Palabra por palabra:

Profesor N. dice tener una prueba de la corrección del algoritmo de Dijkstra. Él afirma que el algoritmo de Dijkstra relaja los bordes de cada ruta más corta en el gráfico en el orden en que aparecen en la ruta, y por lo tanto la propiedad de relajación de ruta se aplica a cada vértice alcanzable desde la fuente. Demuestre que el profesor se equivoca al construir un gráfico dirigido para el cual el algoritmo de Dijkstra podría relajar los bordes del camino más corto fuera de orden.

Answer 1

creo que la frase clave en el texto es que el algoritmo de Dijkstra "relaja los bordes de cada camino más corto en el gráfico ..."

Eso por sí solo es una mentira si hay múltiples caminos más cortos de la mismo costo

Considere este gráfico: A -> B, A -> C, B -> D, C -> D. La fuente es A y el destino es D. Cada peso de borde es 1. Hay dos caminos de A a D, uno a través de B y uno a C. Sin embargo, un borde B-> D o C-> D nunca se relaja.

¿Aún no está convencido porque dijkstra termina antes de evaluar el otro extremo en D? Agregue un borde extra D-> E y establezca el Destino en E. La ruta de A-> D a B tiene el mismo costo que A-> D a C y ambos son más baratos que el costo de A-> E. Sin embargo, nunca relajará el segundo borde en D, ya que el algoritmo solo relaja los bordes a vértices a los que aún no conoce el camino más corto.

Answer 2

Produce un borde único, peso tres, que llega al destino. Ahora agregue una ruta que consta de varias paradas, peso total inferior a tres, que también llegan al destino. Cuando relajas el origen, colorearás el nodo de destino como tres, lo cual es incorrecto. Tienes que continuar relajando todos los nodos más cerca (ruta mínima conocida al destino) hasta que ese conjunto esté vacío. Solo entonces puedes estar seguro de que el algoritmo de D te ha dado la respuesta correcta.

Busque el algoritmo A * para más diversión.

Answer 3

El punto es que la conclusión no se desprende de las premisas, y para construir un contraejemplo. SSSP encuentra todas las rutas más cortas. No hay ninguna razón para que los caminos más cortos deban encontrarse en estricto orden. Considera un árbol-gráfico. Todos los caminos son también los más cortos. Ahora, si relajamos la raíz, entonces no hay un orden particular en los bordes. Pero supongamos que incluso le impuso uno. Luego, después de relajar el nodo no raíz más cercano, es posible que tenga un grupo de bordes realmente largos en el segundo nivel. El siguiente vecino de raíz más cercano puede tener un grupo de bordes salientes muy cortos en esa parte del segundo nivel. En ese caso, relajará los bordes que contribuyen a una longitud de recorrido total MÁS CORTA que otros bordes que ya ha relajado, ya que siempre relajar NODES, no bordes, en el orden de recorrido más corto.

Answer 4

Considere el siguiente gráfico dirigido: (A, B), (A, C), (B, D), (C, D), (D, E) con pesos de borde w (A, B) = 1 , w (A, C) = 1, w (B, D) = 0, w (C, D) = 0, w (D, E) = 1. El vértice fuente es A. Una posible permutación de los bordes relajados en el algoritmo de Dijkstra es (A, B), (A, C), (B, D), (D, E), (C, D). Además, A.d = 0, B.d = 1, C.d = 1, D.d = 1, E.d = 2 después de realizar el algoritmo de Dijkstra. Hay dos caminos más cortos de A a E, uno es ABDE y el otro es ACDE.La contradicción es para el segundo camino, el borde (C, D) debe estar siempre relajado antes (D, E).

Answer 5

Considérese el gráfico:

A--->B A--->C B--->C C--->D 

y dejar que cada arista tiene peso 0.

algoritmos de Dijkstra podría relajar los bordes en el orden

(A,C) (A,B) (C,D) (B,C) 

La gráfica tiene dos rutas más cortas desde A a D, ambos cuestan 0.

A-->B-->C-->D or A-->C-->D 

Los bordes de la ruta más corta {A -> B -> C -> D} se relajan fuera de orden cuando (B, C) se relaja DESPUÉS (C, D).