Projete um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo dirigido acíclico…

Questão

Projete um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo dirigido acíclico (DAG) onde cada vértice v tem atributo duracao[v], calcule para cada vértice o menor tempo de término possível assumindo execução paralela ilimitada (ou seja, respeitar dependências).

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

Resposta esperada

Entrada: lista de adjacência adj[], vetor duracao[v] para cada vértice. 1. Calcular indegree[v] para todos os vértices. 2. Inicializar fila Q vazia e vetor inicio[v] = 0. 3. Enfileirar todos os vértices com indegree 0 em Q. 4. Enquanto Q não estiver vazia: a. u = desenfileirar(Q). b. tempo_termino[u] = inicio[u] + duracao[u]. c. Para cada v em adj[u]: i. Atualizar inicio[v] = max(inicio[v], tempo_termino[u]). ii. Decrementar indegree[v]. iii. Se indegree[v] == 0 então enfileirar v em Q. 5. Ao final, tempo_termino[v] contém o menor tempo de término para cada vértice; o tempo total mínimo é max_v tempo_termino[v]. Complexidade: O(V + E) usando lista de adjacência. Observação: algoritmo corresponde a ordenação topológica (Kahn) propagando tempos de início mais cedo.

Explicação

O algoritmo utiliza a técnica de ordenação topológica para processar os vértices de um grafo dirigido acíclico, garantindo que as dependências entre as tarefas sejam respeitadas. Ao calcular o tempo de término de cada vértice com base nos tempos de término dos predecessores, ele assegura que o tempo total mínimo seja obtido de forma eficiente. A complexidade O(V + E) indica que o algoritmo é escalável e adequado para grafos grandes, mantendo a eficiência na propagação dos tempos.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos…
• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
• Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
• Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
• Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…

Todas as questões de Decomposição