Please enable JavaScript.

Coggle requires JavaScript to display documents.

Outros algorítmos de menor caminho - Coggle Diagram

- - - - 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 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
    - - 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