Floyd-Warshall para Todos os Pares

Às vezes, você precisa do caminho mínimo entre cada par de nós, e não apenas a partir de uma origem. Esse é o problema de todos os pares.

O Floyd-Warshall preenche uma tabela completa de distâncias para todos os pares com três laços aninhados organizados e quase nenhuma preparação.

Use uma matriz em que dist[i][j] é o melhor custo conhecido de i até j. Inicialize-a com as arestas diretas fornecidas.

Todo nó alcança a si mesmo gratuitamente, então defina a diagonal dist[i][i] como zero antes de começar os relaxamentos.

O truque é permitir que os caminhos passem por um nó intermediário k e verificar se passar por k é mais barato que ir diretamente.

O laço externo é k, o ponto intermediário escolhido. Os laços internos i e j testam cada par em relação a esse ponto intermediário.

Para cada par, relaxe passando por k: se ir de i até k e depois até j for mais curto, atualize dist[i][j] para esse custo combinado.

Quando k termina, todos os pares podem usar pontos intermediários até k. Colocar k no laço mais externo mantém essa garantia correta.

O Floyd-Warshall aceita arestas negativas, mas não ciclos negativos. Um ciclo negativo faz alguma entrada da diagonal ficar abaixo de zero.

Três laços sobre n nós resultam em tempo O(n^3) e espaço O(n^2), sendo viável apenas quando n permanece na casa de algumas centenas.

Escolha o Floyd-Warshall quando o grafo for pequeno e denso e você realmente precisar da distância entre cada par, não apenas das distâncias a partir de uma origem.

Inicialize uma matriz, defina a diagonal como zero e percorra k, i, j, relaxando através de k. Caminhos mínimos entre todos os pares em O(n^3). 🧮