Solução Caminho mais largo

0 Flares Facebook 0 0 Flares ×

Solução de João Guilherme

Para ver o problema original, clique aqui.

Esse problema é uma simples modificação do algoritmo de Floyd-Warshall (uma solução usando Djikstra também é possível, e ambas estão contidas no código). Primeiro notamos que a complexidade do algoritmo passa bem no tempo da questão, segundo vemos como o algoritmo funciona, ele pega o melhor caminho do vértice i ao j usando apenas vértices no conjunto {1, 2, ..., k} para cada k de 1 a n. No nosso caso nós definimos o melhor caminho como sendo o que tem a maior aresta mínima, assim em vez de tomar o mínimo entre o caminho que temos de i a j e o caminho de i a k + o caminho de k a j, tomamos o máximo entre o caminho de i a j e o peso mínimo entre as arestas no caminho de i a k e de k a j. Por fim imprimimos a distância entre as duas cidades desejadas.

Segue código para melhor entendimento.

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: