Shortest path in graph

Shortest path in graph

de Santiago Lopez De Haro Grille -
Número de respuestas: 1

No me esta quedando claro si cuando vayamos a computar esta parte, hay que ver los w a los que v tiene un camino, porque en la formula dice todos los w de V, y en el codigo dice: "For v ∈ V in any order" dando a entender que se prueban todos los nodos del grafo, no solo a los que v tiene una arista.

Desde ya muchas gracias.

En respuesta a Santiago Lopez De Haro Grille

Re: Shortest path in graph

de Jonathan Murana -
Hola Santiago,

los v se recorren todos, es decir, se recorre toda la matriz. En esa recorrida, para cada celda, se recorren eventualmente n celdas (las correspondientes a la columna i-1) para buscar un mínimo. En la búsqueda del mínimo sí, solo se consideran los nodos adyacentes, por ejemplo si el grafo estuviera con una estructura de listas de adyacencias sería fácil. Otra alternativa es decir que si los nodos no son adyacentes la "arista" tiene costo infinito, pero esto no es del todo eficiente si miras la sección siguiente del libro que habla de mejorar el tiempo de este algoritmo.

Espero haber respondido tu pregunta.
Saludos.