Por que o DFS não pode ser usado para encontrar caminhos mais curtos em gráficos não ponderados?

Entendo que o uso do DFS "como está" não encontrará o caminho mais curto em um gráfico não ponderado.

Mas por que ajustar o DFS para permitir encontrar caminhos mais curtos em gráficos não ponderados é uma perspectiva tão impossível? Todos os textos sobre o assunto simplesmente afirmam que isso não pode ser feito. Não estou convencido (sem ter tentado eu mesmo).

Você conhece alguma modificação que permita ao DFS encontrar os caminhos mais curtos em gráficos não ponderados? Se não, qual é o algoritmo que o torna tão difícil?

O único elemento da pesquisa aprofundada que você ajusta é a ordem em que as crianças são investigadas. A versão normal prossegue em ordem arbitrária, ou seja, na ordem em que os filhos são armazenados.

A única alternativa viável (em direção aos caminhos mais curtos) que posso encontrar é uma abordagem gananciosa, que é olhar as crianças em ordem de distância do nó atual (do pequeno ao grande). É fácil construir um contra-exemplo para esta regra:

^{[ fonte ]}

Agora, isso não prova que não existe uma estratégia de escolher o próximo filho a ser investigado, o que fará com que o DFS encontre os caminhos mais curtos.

$(s,t)$$(s,a)$$a$$(a,b)$$(s,t)$ . Portanto, é plausível que o DFS nunca encontre caminhos mais curtos (em gráficos gerais).

$c$$c-1$

1. Contanto que a regra seja determinística. Caso contrário, nem sempre é possível encontrar caminhos mais curtos.

Largura pesquisa de é o algoritmo que encontrará os caminhos mais curtos em um gráfico não ponderado.

Há um ajuste simples para passar do DFS para um algoritmo que encontrará os caminhos mais curtos em um gráfico não ponderado. Essencialmente, você substitui a pilha usada pelo DFS por uma fila. No entanto, o algoritmo resultante não é mais chamado DFS. Em vez disso, você implementou a primeira pesquisa de largura.

O parágrafo acima fornece a intuição correta, mas simplifica um pouco a situação. É fácil escrever código para o qual a troca simples fornece uma implementação da primeira pesquisa abrangente, mas também é fácil escrever código que, a princípio, parece uma implementação correta, mas na verdade não é. Você pode encontrar uma pergunta relacionada ao cs.SE no BFS vs DFS aqui . Você pode encontrar um bom pseudo-código aqui.

Você pode!!!

Marque os nós como visitados enquanto estiver em profundidade e desmarque quando retornar, enquanto retorna quando encontra outro (s) ramo (es) repetindo o mesmo.

Salve o custo / caminho para todas as pesquisas possíveis em que você encontrou o nó de destino, compare todo o custo / caminho e escolha o menor.

O grande problema (e refiro-me a BIG) dessa abordagem é que você visitaria o mesmo nó várias vezes, o que torna o dfs uma péssima escolha óbvia para o algoritmo de caminho mais curto.

O BFS possui uma boa propriedade que verifica todas as arestas da raiz e mantém a distância da raiz até os outros nós o mínimo possível, mas o dfs simplesmente salta para o primeiro nó adjacente e é aprofundado. Você PODE modificar o DFS para obter o caminho mais curto, mas você só terminará em um algoritmo com maior complexidade de tempo ou que fará o mesmo que o BFS

É possível encontrar o caminho entre dois vértices com o número mínimo de arestas usando o DFS. podemos aplicar uma abordagem de nível

Você pode

basta percorrer o gráfico da maneira DFS e verificar

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Aqui está o link para a solução completa