O que é um caminho mínimo em um gráfico?

Question

Em teoria dos grafos, o que é a distinção entre a distância mínima (que encontra o algoritmo de Dijkstra), e caminho mínimo (que eu não sei o que é)?

Answer 1

caminho mínima é o conjunto de arestas que quando atravessado abrangem a menor quantidade de distância entre as duas arestas. distância mínima é a soma da distância entre as bordas de um caminho mínimo.

Answer 2

distância é escalar; um número. caminho é uma lista de pares vertex / edge?

Answer 3

= distância mínima menos, soma dos pesos das arestas. caminho mínima = menos arestas.

Ie // É um caminho mais curto para voar a partir de Vancouver para Toronto e depois para Winipeg mesmo que seja uma distância mais curta para voar a partir de Vancouver a Calgary para Regina e depois para Winipeg.

Editar: Falhanços que cerca eu acho.

Answer 4

Eu não estou 100% de certeza, mas parece que o caminho mínima seria a lista de vértices visitados ao atravessar o caminho mínima distância do vértice A ao vértice B.

Answer 5

Deixe-me responder a esta questão no âmbito de uma rede com uma fonte e uma pia. Gostaria de distinguir entre um caminho mais curto e um caminho mínima, em que um caminho é definido por um conjunto de arestas.

Um caminho mais curto é um caminho da origem ao pia que tem a menor distância correspondente. Um caminho mínima pode ser qualquer caminho que liga a fonte para a pia enquanto

i) não contém ciclos; e

ii) remoção de qualquer das extremidades dos meios de percurso que já não há uma conexão entre a fonte e dreno.

Answer 6

distância mínima é o mesmo que caminho mínimo.