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

• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…
• Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
• Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
• Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…

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