1 votos

Algoritmo de Dijkstra - ¿dos soluciones posibles?

Hice una pregunta de tarea, que consistía en elegir el camino más corto hacia los otros puntos desde un punto usando el algoritmo de Dijkstra.

Terminé con lo siguiente, mientras que una aplicación en línea resultó en algo diferente (el gráfico superior es mi intento, el inferior es el de la aplicación): gráficos

(Los vértices en la segunda imagen tienen nombres diferentes, pero traté de usar la misma forma del gráfico.)

Entonces, en lugar de B-D, hice E-D. Para D, las rutas B-D y B-E-D tienen la misma longitud, así que me preguntaba si ambas son realmente correctas.

Gracias.

4voto

Rudy the Reindeer Puntos 20855

La solución al problema de la ruta más corta no es única.

Imagina que tienes un grafo de 2 nodos, llamémosles A y B. Tienes, digamos, 10 aristas entre ellos, todas de peso igual w. Entonces, la ruta más corta de A a B es cualquiera de estas 10 aristas, por lo que la solución no es única. En particular, depende del orden en el que se recorren los nodos en cada iteración.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X