¿Qué es una ruta mínima en un gráfico?

Question

En la teoría de gráficos, ¿cuál es la distinción entre la distancia mínima (que encuentra el algoritmo de Dijkstra) y la ruta mínima (que no estoy seguro de qué es)?

Answer 1

La ruta mínima es el conjunto de bordes que, cuando se atraviesan, cubren la menor distancia posible entre dos bordes. La distancia mínima es la suma de la distancia entre los bordes de una ruta mínima.

Answer 2

la distancia es escalar; un número. ruta es una lista de pares de vértices / bordes?

Answer 3

Distancia mínima = menor suma de pesos de arista. Ruta mínima = menos aristas.

Es decir, es un camino más corto para volar de Vancouver a Toronto y luego a Winipeg, aunque es una distancia más corta para volar de Vancouver a Calgary a Regina y luego a Winipeg.

Editar: Dale la vuelta, creo.

Answer 4

No estoy 100% seguro, pero parece que la ruta mínima sería la lista de vértices visitados al atravesar la ruta de distancia mínima desde el vértice A al vértice B.

Answer 5

Permítanme responder esta pregunta dentro del alcance de una red con una fuente y un sumidero. Me gustaría distinguir entre una ruta más corta y una ruta mínima, donde una ruta está definida por un conjunto de bordes.

Una ruta más corta es una ruta desde el origen hasta el sumidero que tiene la distancia correspondiente más corta. Una ruta mínima puede ser cualquier ruta que conecte la fuente al sumidero siempre que

i) no contiene ciclos; y

ii) la eliminación de cualquiera de los bordes de la ruta significa que ya no hay una conexión entre la fuente y el sumidero.

Answer 6

La distancia mínima es igual a la ruta mínima.