Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite…

Questão

Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de velocidade (km/h), descreva em pseudocódigo um algoritmo que, usando listas de adjacência, encontre o caminho que minimiza o tempo total de viagem. Explique as estruturas usadas e a complexidade.

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

Resposta esperada

Modelo de resposta (pseudocódigo e justificativa): Dados: G(V,E) com para cada aresta e: distância d(e) e limite s_lim(e). Representação: listaAdj[v] = lista de pares (u, d, s_lim). Peso temporal de e: t(e) = d(e) / s_lim(e) (assume-se viajar à velocidade máxima permitida). Pseudocódigo (Dijkstra sobre tempo): inicializar dist[v]=8 para todo v; dist[orig]=0 fila = prioridade com (orig,0) while fila não vazia: (v, tv) = extrair mínima if tv>dist[v] continue for cada (u,d,s_lim) in listaAdj[v]: alt = dist[v] + d / s_lim if alt < dist[u]: dist[u] = alt prev[u] = v atualizar fila com (u,alt) Ao final, reconstruir caminho via prev até destino. Complexidade: O((V+E) log V) com heap binário; armazena apenas listas de adjacência e vetores dist/prev. Observações: se o veículo não puder atingir s_lim, ajustar t(e)=d/velocidade_real; para velocidades variáveis ou tráfego, usar funções de custo por aresta e manter propriedade nonnegativa para Dijkstra.

Explicação

O algoritmo proposto utiliza a abordagem de Dijkstra, que é adequada para encontrar o caminho mais curto em grafos ponderados, adaptando o peso das arestas para representar o tempo de viagem. A estrutura de lista de adjacência permite uma representação eficiente do grafo, facilitando a exploração dos vizinhos de cada vértice. A complexidade do algoritmo, O((V+E) log V), garante eficiência mesmo em grafos grandes, tornando-o prático para resolver o problema proposto.

Raio-X da questão

Questões parecidas com resolução

• Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
• Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
• — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
• Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
• — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
•  Ontem o mapa do festival me mandou dar uma volta enorme  reclamou uma visitante. Para reduzir aglomeracoes, a…

Todas as questões de Programação - Programação usando grafos e árvores