Dúvida Lab 12

[leo-leao]

Para este Lab vocês esperam que a gente implemente o algoritmo de Dijkstra ou devemos procurar soluções mais simples?

[iagoac]

@leo-leao o algoritmo de Dijkstra computa o caminho mais curto entre dois vértices em um grafo.
O objetivo deste laboratório é encontrar o segundo menor caminho entre dois vértices, coisa que o Dijkstra não faz.

[leo-leao]

Prof @iagoac , estou com muita dificuldade de formular uma saída para a resolução do Lab, visto que nas aulas nos foram apresentados a resolução de caminho mínimo pelo algoritmo de Djikstra e o caminho mínimo por busca em profundidade/largura para o caso em que não possuímos pesos.

Os casos que já consegui pensar é uma adaptação de Djikstra para que, dado um caminho mínimo, o meu código tente encontrar o segundo menor caminho "cancelando" um ou mais vertices do caminho mínimo. Só que penso que isso seja inviável pelo tempo de execução.

Você poderia, por gentileza, me dar pelo menos uma dica ou caminho para resolução? Venho a dias quebrando a cabeça com isso e não consigo de forma alguma encontrar algo que me agrade.

[iagoac]

É exatamente o que você disse. Como o grafo contém pesos nas arestas, algoritmos de busca em profundidade ou largura não servem de nada neste problema.

Existem diversas soluções para o problema do segundo caminho mais curto em um grafo, sendo que a maioria delas envolve a modificação do algoritmo de Dijkstra.

Uma adaptação de Djikstra para que, dado um caminho mínimo, o meu código tente encontrar o segundo menor caminho "cancelando" um ou mais vertices do caminho mínimo

Pense em "cancelar" uma aresta ao invés de um vértice. Acho que fica mais fácil o seu pensamento a partir daí.

[leo-leao]

Certo! Continuarei nessa caminho então, como implementei o Djikstra por matriz de adjacências creio que ficará fácil cancelar uma aresta, como sua sugestão! Muito obrigado professor!

[leo-leao]

Prof @iagoac , eu implementei o método que discutimos acima, dos testes aberto que deram certo: 1, 2, 3, 4, 7, 8. Entretanto tive problemas com o 5, 6, 9 e 10. Existe casos em que eu devo "cancelar" mais de uma aresta? No caso, eu implementei meu código de modo que, toda vez que eu testava "cancelar" uma aresta, logo após a detecção do caminho mínimo, eu retornava os pesos para a minha matriz de adjacências. @enoque se puder dar uma luz no fim do tunel tbm kkk

[iagoac]

Existe casos em que eu devo "cancelar" mais de uma aresta?

Sim, e eu vou dar um exemplo abaixo.

---

Considere este grafo com 8 vértices e 9 arestas. O objetivo é encontrar o segundo caminho mais curto entre x e y.

Pode-se observar que o caminho mais curto, como marcado em vermelho, percorre x->a->b->c->y e tem custo 4.

Já o segundo caminho mais curto percorre o caminho x->a->f->y e tem custo 5.

Do caminho mais curto para o segundo caminho mais curto, foi preciso remover (ou "cancelar") três arestas: (a,b), (b,c) e (c,y). Além disso, duas novas arestas foram adicionadas: (a,f) e (f,y).

[leo-leao]

Mas note que, se eu cancelar somente a aresta (c,y) meu menor caminho caminho obrigatoriamente ja é o apresentando, logo nesse exemplo eu não precisaria cancelar mais de uma aresta. Existe uma quantidade de aresta normal para retirar na próxima análise? Por que eu tenho medo do código acabar ficando lento

EDIT: Prof @iagoac , eu fiz uma alteração boba em meu código e agora ele passa nos testes de 1 à 8, não passando no 9 e 10. Nos fechados é informado a mensagem de tempo excedido, teria como aumentar o tempo de processamento no susy?