Encontre o caminho mais curto entre dois nós (vértices)

Question

Eu tenho uma lista de arestas interligados (E), como posso encontrar o caminho mais curto conectando a partir de um vértice para outro?

Estou pensando em usar mais ancestrais comuns , mas o bordas não têm uma raiz claramente definida, então eu não acho que as obras de solução.

caminho mais curto é definido pelo número mínimo de vértices percorridos.

Nota: Não poderia ser um multi-caminho que liga dois vértices, então obviamente em largura primeira pesquisa não funcionará

Answer 1

Eu não tenho certeza se você precisa de um caminho entre todas par de nós ou entre dois particulares nós. Desde que alguém já deu uma resposta abordar o primeiro, vou abordar o último.

Se você não tem qualquer conhecimento prévio sobre o gráfico (se você fizer isso, você pode usar uma pesquisa baseada em heurística, como a * ), então você deve usar um em largura pesquisa .

Answer 2

algoritmo de Dijkstra vai fazer isso por você.

Answer 3

O Floyd-Warshall algoritmo seria uma possível solução para o seu problema, mas há também outras soluções para resolver o todos os pares menor problema do caminho.

Answer 4

Shortest path is defined by the minimum number of vertexes treversed

é igual ao número mínimo de arestas mais um.

Você pode usar largura padrão primeira pesquisa e ele vai funcionar bem. Se você tem mais de um caminho que liga dois vértices apenas salvar um deles não vai afetar nada, porque o peso de cada borda é 1.

Answer 5

adicionais 2 centavos. Dê uma olhada na NetworkX . Há algos interessantes já implementados para o que você precisa, e você pode escolher o mais adequado.