Please enable JavaScript.
Coggle requires JavaScript to display documents.
M13, :, : - Coggle Diagram
M13
Iteração
Para cada vértice intermediário k, atualize a matriz de distâncias considerando que o caminho mais curto entre dois vértices i e j pode passar por k.
A atualização é feita da seguinte forma: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
-
-
Inicialização
Crie uma matriz de distâncias dist[][], onde dist[i][j] representa a menor distância do vértice i ao vértice j.
Inicialize dist[i][j] com o peso da aresta que conecta i a j. Se não houver aresta, inicialize com infinito (exceto dist[i][i], que é 0).
Complexidade
Tempo de execução: O(V^3), onde V é o número de vértices.
Espaço de execução: O(V^2), devido à matriz de distâncias.
Vantagens
-
Capaz de lidar com pesos negativos, desde que não haja ciclos negativos.
-
Definição
Algoritmo usado para encontrar os caminhos mais curtos entre todos os pares de vértices em um grafo ponderado.
-
Pode lidar com pesos negativos, mas não com ciclos negativos.
Conclusão
Após considerar todos os vértices intermediários, a matriz dist[][] conterá as menores distâncias entre todos os pares de vértices.
-
-
-