Em um grafo ponderado onde cada aresta tem duas informações: capacidade (número máximo de veículos) e custo…

Questão

Em um grafo ponderado onde cada aresta tem duas informações: capacidade (número máximo de veículos) e custo (combustível), descreva um algoritmo em linguagem descritiva que calcule, entre um vértice origem e um vértice destino, um caminho que maximize a capacidade mínima ao longo do caminho e, entre os que atingem essa capacidade, minimize o custo total. Use os termos algoritmo, grafo e variável.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Modelo de resposta (algoritmo): 1) Inicialize para cada vértice v duas variáveis: cap[v] = -8, custo[v] = +8; cap[origem] = +8, custo[origem] = 0; pred[v]=nulo. 2) Use uma fila de prioridade que ordena por (cap desc, custo asc). 3) Enquanto fila não vazia: extrair u; para cada aresta (u,v) com capacidade ce e custo ceu: novaCap = min(cap[u], ce); novoCusto = custo[u] + ceu; se novaCap > cap[v] ou (novaCap == cap[v] e novoCusto < custo[v]) então atualizar cap[v]=novaCap, custo[v]=novoCusto, pred[v]=u e inserir/atualizar v na fila. 4) Ao terminar, reconstrua o caminho a partir de pred[destino]. Complexidade: O((V+E) log V) com fila de prioridade. Explicação: a prioridade maximiza primeiro a capacidade mínima (critério principal) e usa custo como critério de desempate, garantindo o caminho desejado.

Explicação

O algoritmo proposto utiliza uma abordagem eficiente para explorar o grafo, priorizando a maximização da capacidade mínima ao longo do caminho, o que é essencial para garantir que o caminho escolhido suporte o maior número possível de veículos. Além disso, ao empregar uma fila de prioridade que considera o custo como critério de desempate, o algoritmo assegura que, entre os caminhos com a mesma capacidade, o menor custo total de combustível seja selecionado. Essa combinação de critérios permite encontrar um caminho ótimo que atende aos requisitos do problema de forma eficaz.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
• Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…
• Desenvolva um algoritmo que encontre o caminho mais curto em um grafo representando uma rede de computadores. Descreva…

Todas as questões de Listas e grafos