---

Algoritmo de Menor Caminho com Restrição de Explosões

Este projeto implementa uma solução eficiente para encontrar o menor caminho em um grafo onde os vértices possuem tempos limite de explosão. O algoritmo combina a utilização de uma Fila de Prioridade (Min-Heap) e o Algoritmo de Dijkstra, adaptado para lidar com as restrições impostas pelos tempos de explosão. O projeto foi desenvolvido como parte do Trabalho 03 da disciplina CTCO04 - Projeto e Análise de Algoritmos.

Objetivos

• Implementar um algoritmo para calcular o menor caminho em um grafo com restrições de tempo.
• Garantir que o caminho encontrado seja válido, ou seja, o vértice de destino seja alcançado antes de explodir.
• Demonstrar a aplicação de algoritmos de grafos eficientes para resolver problemas práticos envolvendo restrições temporais.

Algoritmo de Dijkstra Modificado

O Algoritmo de Dijkstra é utilizado para calcular o menor caminho a partir de um vértice inicial até os demais vértices do grafo. Neste projeto, o algoritmo foi modificado para levar em consideração o tempo de explosão de cada vértice, descartando caminhos inviáveis.

Adaptações para o Problema

1. Fila de Prioridade (Min-Heap):

   • Utilizada para selecionar o próximo vértice a ser processado com base no menor tempo acumulado.
   • Permite que o algoritmo funcione com eficiência O((V + E) log V), onde (V) é o número de vértices e (E) o número de arestas.

2. Restrições de Explosão:

   • Cada vértice tem um tempo limite de explosão.
   • Um vértice só pode ser incluído no caminho se for alcançado antes de seu tempo limite.

Estrutura do Projeto

• Grafo: Representado como uma lista de adjacência para armazenar os vértices e suas arestas.
• Fila de Prioridade (Min-Heap): Implementada para garantir que os vértices sejam processados na ordem correta (menor tempo acumulado).
• Algoritmo de Dijkstra: Adaptado para lidar com o tempo limite de explosão dos vértices.

Execução

O programa deve ser executado fornecendo a descrição do grafo, os tempos de explosão dos vértices e a indicação de quais vértices possuem baús. O menor caminho até um dos baús será exibido, desde que seja alcançado antes de explodir.

Exemplo de Entrada

5 6
1 1 6 4 7
0 0 1 0 1
0 1 2
0 3 3
0 4 6
1 2 1
2 3 2
2 4 3

Exemplo de Saída

Sua solução funciona e tem custo: 5

Considerações Finais

Este projeto demonstra como algoritmos clássicos podem ser adaptados para resolver problemas mais complexos, como restrições temporais em grafos. A combinação de uma estrutura eficiente (Fila de Prioridade) com o Algoritmo de Dijkstra permite que soluções otimizadas sejam encontradas mesmo em cenários com restrições adicionais, como os tempos de explosão.

---