Outros algorítmos de menor caminho
Floyd-Warshall algorithm
Bellman-Ford algorithm
Abordagem
Complexidade
Objetivo
Aplicação
Resultado
Processos
Encontrar os caminhos mais curtos entre todos os pares de vértices em um grafo direcionado ou não-direcionado, com ponderações nas arestas
O algoritmo utiliza programação dinâmica para construir uma matriz de distâncias. Cada entrada (i, j) representa a menor distância entre os vértices i e j. A matriz é inicializada com os pesos das arestas diretas
O algoritmo possui uma complexidade de tempo de O(V^3), onde V é o número de vértices no grafo. É eficiente para grafos menores, mas pode ser lento para grafos maiores.
O algoritmo de Floyd-Warshall é valioso para resolver problemas de otimização de caminhos mais curtos, como em redes de transporte, roteamento de redes de computadores e análise de distâncias em sistemas geográficos
Inicialização
Iterações
FInalização
A matriz de distâncias é preenchida com os pesos das arestas diretas entre os vértices
Para cada vértice intermediário k, a matriz de distâncias é atualizada com a fórmula: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Isso considera a possibilidade de encontrar caminhos mais curtos passando por k
Ao fim das iterações, a matriz de distâncias contém as menores distâncias entre todos os pares de vértices
O algoritmo lida com grafos que possuem arestas com pesos negativos, mas não funciona em casos com ciclos de peso negativo acessíveis a partir do vértice de partida
Uma matriz de distâncias contendo as menores distâncias entre todos os pares de vértices, permitindo identificar os caminhos mais curtos em um grafo ponderado
Complexidade
Aplicação
Abordagem
Processos
Objetivo
Resultado
Encontrar os caminhos mais curtos entre um vértice de partida e todos os outros vértices em um grafo direcionado ou não-direcionado, inclusive em casos com arestas de peso negativo e ciclos negativos alcançáveis
O algoritmo de Bellman-Ford utiliza uma abordagem de relaxamento, onde as estimativas de distância para os vértices são iterativamente ajustadas para se aproximarem das distâncias mais curtas
O algoritmo de Bellman-Ford possui uma complexidade de tempo de O(V * E), onde V é o número de vértices e E é o número de arestas no grafo. Ele é mais lento que o algoritmo de Dijkstra, mas é capaz de lidar com arestas de peso negativo e detectar ciclos negativos
O algoritmo de Bellman-Ford é usado em situações onde há possibilidade de existência de arestas de peso negativo e é necessário detectar ciclos negativos. Ele é útil em problemas de roteamento, análise de redes e em algoritmos de fluxo máximo
Iterações
Verificação de Ciclo Negativo
Inicialização
A distância estimada para o vértice de partida é definida como zero, e as distâncias estimadas para todos os outros vértices são definidas como infinito
O algoritmo realiza V - 1 iterações (V sendo o número de vértices), onde em cada iteração, ele relaxa todas as arestas do grafo, ou seja, verifica se passar por uma determinada aresta levaria a um caminho mais curto até o vértice de destino. O processo de relaxamento envolve comparar a distância estimada até o momento com a distância através da aresta, e, se a distância através da aresta for menor, atualiza-se a estimativa de distância para o vértice de destino
pós as V - 1 iterações, é realizada uma iteração adicional para verificar se há ciclos negativos. Se a distância estimada de um vértice ainda puder ser melhorada após a V-ésima iteração, isso indica a presença de um ciclo negativo alcançável
O algoritmo de Bellman-Ford fornece as distâncias mais curtas a partir de um vértice de partida para todos os outros vértices, mesmo em grafos com arestas de peso negativo e ciclos negativos alcançáveis. Se um ciclo negativo for detectado, o algoritmo informará sua existência