¿Cuál es el camino más corto de Dijkstra para el siguiente gráfico?

Desde el estado A, el valor más corto es 7 (en comparación con 10), por lo que la transición ocurre A-> D

ahora estamos en D, puedes ir a B o E ya que el costo es el mismo (3), entonces tomamos B. ahora el costo de A -> B es 10 (a través de D) que es igual a A-> B = 10 (directamente),

entonces el costo A-> B enlace directo se elimina ya que aumentará el costo de A-> D de 10 a 12 (10 + 2, a través de B)

ahora estamos en B, el único enlace es el costo de C es 2. y el costo de A-> C es 12 ahora, tanto a través del nodo B (7 + 3 + 2) como del nodo D (7 + 5) para que podamos eliminar enlace de B a C o de D a C.

ahora estamos en C, el costo de transición de C a E es 6, que es más alto que el costo de

D a E = 3, por lo que podemos eliminar el enlace de C-> E.

ahora estamos en E, hay dos enlaces, primero E a C que cuestan 4 pero no necesitamos ese enlace ya que ya existe un enlace de A a C.

y el otro enlace es A a E y tampoco necesitamos este enlace.

entonces el camino más corto será el siguiente:

A-> D (7)

D-> B (3)

B-> C (2)

D-> E (3)

COSTE TOTAL = 15

Creo que aquí estás hablando del padre del vértice (v).
También supongo que conoces el algoritmo.
Elegimos el vértice (u¹) que tiene un valor mínimo de la cola de prioridad mínima. Entonces, después de la relajación del vértice (v), si la condición es verdadera para la relajación, entonces el vértice (u¹) es el padre del vértice (v).

Relex (u, v, w) {

If (vd

vd = u: d + w (u, v);

v.parent = u;

}

}

Y ahora si hay algún otro vértice (u²) que sea capaz de ser padre del vértice (v). El vértice (u¹) será el padre del vértice (v) porque si ve el código en la función Relájese (u, v , w) la condición

vd

vd es menor que, no menor que igual a.
Entonces, el vértice (u¹) será el padre del vértice (v) en lugar del vértice (u²).

Si tiene alguna pregunta, no dude en preguntar.

La ruta más corta en este caso es A> D> E.

Si encuentra más de un valor más corto en una fila (tercera fila en este caso. Consulte la imagen a continuación). Puedes comenzar con cualquiera de ellos.

He mostrado los dos casos aquí. La respuesta es la misma en ambos casos.

Nota: a veces puede encontrar más de una ruta que tiene el mismo peso más corto. No se preocupe, si comienza con alguna de ellas obtendrá la ruta más corta.

Cualquiera de los nodos está bien si los nodos tienen valores iguales, aunque la convención general para romper los lazos es el orden alfabético: esto produce AD, DB, DE, BC como el árbol de rutas más cortas a partir de A.