Floyd-Warshall

Nesta lição, aprenderemos como resolver o seguinte problema:

Dado um grafo direcionado com pesos com vértices e arestas onde todos os pesos são não-negativos, encontre o caminho mínimo entre todos os pares de vértices

Considere que os vértices são -indexados.

Para o resolver, podemos apenas executar um algoritmo Dijkstra para cada vértice como uma fonte. A nossa complexidade será ou . Esta solução pode ser suficiente para alguns problemas. Mas há um algoritmo que é mais fácil de implementar e que pode ser mais rápido: Algoritmo de Floyd-Warshall.

O algoritmo de Floyd-Warshall utiliza uma programação dinâmica. Seja o menor caminho do vértice para o vértice , de modo a que só possamos utilizar os vértices como vértices intermédios. Há três casos base:

• : esta é igual a
• com tal que há uma aresta de para com peso : vamos definir esta para porque não podemos usar nenhum vértice no caminho, por isso temos de usar esta aresta para passar de para
• com tal que não há uma aresta de para : precisamos definir esta para porque não podemos passar de para sem usar qualquer vértice intermediário

Se tivermos esta , o caminho mais curto entre os vértices e será . Se , significa que não há um caminho entre os vértices e .

Para calcular , precisamos de tratar de dois casos:

• Não usaremos o vértice no caminho ótimo de : neste caso, só usaremos (possivelmente) os vértices como vértices intermediários, por isso a resposta é
• Usaremos o vértice no caminho ótimo de : neste caso, podemos quebrar o caminho mínimo de para nos caminhos mínimos de para e de para . Portanto, a resposta é . Note-se que só estamos a considerar os vértices como vértices intermediários destes dois caminhos porque, se utilizarmos , estaríamos criando um caminho que contém um ciclo, o que não é ótimo.