b'\n_START_ARTICLE_\nAlgoritmo de Dijkstra\n_START_SECTION_\nProblemas relacionados\n_START_PARAGRAPH_\nO algoritmo de Dijkstra n\xc3\xa3o consegue encontrar o menor caminho em um grafo com pesos negativos. Para esse prop\xc3\xb3sito, pode-se usar o algoritmo de Floyd-Warshall, que consegue descobrir a menor dist\xc3\xa2ncia entre todos os pares de v\xc3\xa9rtices de qualquer grafo sem ciclos com peso negativo em uma complexidade de tempo O(V\xc2\xb3). Se o problema n\xc3\xa3o exigir o c\xc3\xa1lculo da dist\xc3\xa2ncia entre todos os pares de v\xc3\xa9rtices ou se existirem ciclos com peso negativo, pode-se aplicar o algoritmo de Bellman-Ford, com complexidade de tempo O(V*E)._NEWLINE_Em uma \xc3\xa1rvore, \xc3\xa9 poss\xc3\xadvel encontrar a dist\xc3\xa2ncia entre um v\xc3\xa9rtice inicial e todos os outros v\xc3\xa9rtices em tempo O(V+E), utilizando busca em profundidade (tamb\xc3\xa9m conhecida como DFS). Em um grafo cujas arestas t\xc3\xaam todas o mesmo peso, pode-se encontrar a dist\xc3\xa2ncia entre um v\xc3\xa9rtice inicial e todos os outros v\xc3\xa9rtices, para um grafo qualquer, em O(V+E), utilizando busca em largura (tamb\xc3\xa9m conhecida como BFS)._NEWLINE_O processo utilizado no algoritmo de Dijkstra \xc3\xa9 bastante similar ao processo usado no algoritmo de Prim. O prop\xc3\xb3sito deste \xc3\xbaltimo, entretanto, \xc3\xa9 encontrar a \xc3\xa1rvore geradora m\xc3\xadnima que conecta todos os n\xc3\xb3s de um grafo. O BFS pode ser visto como um caso especial do algoritmo de Dijkstra em grafos n\xc3\xa3o dirigidos, onde a fila de prioridade assume o comportamento FIFO.'