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

• Uma escola criou um grafo para representar as relações entre as disciplinas que os alunos devem estudar. Se a disciplina…
• Descreva como um grafo pode ajudar a otimizar rotas de entrega em uma empresa de logística.
• Um mapa mostra cinco cidades e as estradas diretas entre elas. As estradas existentes são: A–B, A–C, B–D e C–E. Não há…
• Antes de ir à feira, Bia anotou: pão, bananas e sabonete. Que objeto do dia a dia é esse e como Bia pode mudar a ordem…
• No mapa da sala, há círculos para a porta, a mesa da professora, a estante e o quadro. As linhas ligam porta-mesa…
• — A mensagem não chegou ao abrigo do bairro Serra — avisou uma moradora pelo rádio comunitário. Após a enchente, a…

Todas as questões de Listas e grafos