Universidade Federal de Pernambuco 
Centro de Informática

IF672 - Algoritmos e Estruturas de Dados
junho a setembro de 2002

1. Faça um programa para, dada uma árvore binária, determinar, para cada vértice v, qual o comprimento do caminho mais longo entre todos os caminhos que ligam pares de descendentes de v (incluindo v). O procedimento deve ser feito bottom-up e, ao deixar cada nó, esta informação já deve estar armazenada nele. O programa deve imprimir o maior caminho em toda a árvore (em in-ordem).

Observação: Observe que o caminho mais longo entre todos os caminhos que ligam pares de descendentes de v não necessariamente passa por v.

2. Modifique o algoritmo Distâncias, apresentado em sala de aula, para identificar quantos caminhos diferentes de comprimento mínimo existem para cada vértice de um grafo, a partir de um dado vértice.

Atenção: A escolha do vértice de menor custo acumulado a cada iteração do algoritmo deve ser feita de maneira eficiente, utilizando um Heap.