Eu fiz essa pergunta no StackOverflow. Me pediram para morar aqui. Então aqui está:
Preciso de alguns esclarecimentos e informações sobre o algoritmo de Dijkstra versus a primeira pesquisa de largura em gráficos direcionados, se estiverem corretos.
O algoritmo de Dijkstra encontra o caminho mais curto de Nó Apara Nó Fem um gráfico ponderado, independentemente de haver ou não um ciclo (desde que não haja pesos negativos)
mas para isso, todos os caminhos de Apara todos os outros nós no gráfico são calculados e pegamos o caminho de Apara Finvertendo as seqüências de nós em prev.
BFS: localiza o caminho mais curto de nó Apara nó Fem um gráfico não ponderado, mas se falhar se um ciclo for detectado.
no entanto, o BFS apenas calcula o caminho do nó A para o nó F e não necessariamente todo o caminho do nó A. Se o nó F for alcançado mais cedo, ele retornará o caminho.
fonte
Embora a resposta de Aditya seja boa, gostaria de esclarecer alguns pontos.
Primeira pesquisa de largura
A Pesquisa por Largura (BFS) apenas usa uma fila para enviar e enviar nós de / para. Isso significa que ele visita os nós na ordem de sua profundidade.
Se acontecer que o custo de todos os operadores é o mesmo (para que sejam considerados iguais a 1), é garantido que você encontrará uma solução ideal.
Como conseqüência, observe o seguinte:
Apenas enumera caminhos até que a solução seja encontrada. Não se pode dizer que esse algoritmo calcula o caminho mais curto entre o nó de origem e o nó de objetivo (ponto final!). Ele apenas calcula a distância de todos os caminhos que encontra no caminho em direção à meta. Em outras palavras, o que for dito sobre o caminho que ele encontra para o nó de objetivo pode ser igualmente dito sobre qualquer outro caminho descoberto por ele.
Nada impede que o BFS seja aplicado a gráficos com custos arbitrários. O único ponto a ser lembrado é que o algoritmo preserva a integridade (para que seja garantido encontrar uma solução), embora a admissibilidade seja perdida (ou seja, não garante que a solução seja ótima).
Originalmente, o BFS não considerava uma lista FECHADA para armazenar todos os nós expandidos, de modo que você está certo quando diz que pode cair em um ciclo. No entanto, como ele armazena explicitamente todos os nós na memória e a camada com maior demanda de memória é sempre a mais recente, o BFS geralmente é estendido com uma lista FECHADA que armazena todos os nós expandidos anteriormente. Se uma transposição for encontrada antes da expansão de um nó, ela poderá ser ignorada com segurança.
Algoritmo de Dijkstra
De fato, se você adicionar uma lista CLOSED ao BFS, conforme sugerido no ponto 3 acima, e também classificar os nós na pilha (a chamada lista OPEN) em ordem crescente de (ou seja, o custo do caminho a partir do start state para ), então você tem o algoritmo de Dijkstra (bem, há também outra diferença muito importante, enquanto o BFS para ao gerar o nó de objetivo, o Dijkstra para ao expandi- lo).g(n) n
Assim:
Novamente, esse algoritmo apenas enumera caminhos até que a solução seja encontrada. Não é verdade que ele visite todos os nós no espaço de estados e, de fato, o algoritmo de Dijkstra é conhecido por estar completo (isto é, garante que uma solução seja encontrada, se houver), mesmo que o gráfico subjacente seja infinito.
Você pode aplicar com segurança o algoritmo de Dijkstra quando as operações tiverem custos arbitrários. De fato, essa é a razão pela qual você substituiu a fila por um heap em que os nós são inseridos em ordem crescente de custo.
Edgar Dijkstra originalmente considerou usar uma lista FECHADA (você pode conferir o artigo dele, é apenas algumas páginas e é muito fácil de ler) para que os ciclos sejam considerados adequadamente.
Espero que isso ajude, talvez seja necessária uma explicação mais detalhada desses algoritmos. Se sim, não hesite em pedir por eles
Felicidades,
fonte