Lista 5
Antes de fazer
estes exercícios, leia com atenção textos sobre
Grafos, Busca
em Largura, Busca em Profundidade, Distâncias, Árvore de
Custo Mínimo e
algoritmos greedy em geral
2. Dado um grafo G = (V,E) com pesos, achar o grafo G' tal
que para cada 2 vértices Vi e Vj de G, o peso da aresta
ligando Vi e Vj no grafo G' seja o menor caminho entre
Vi e Vj no grafo G, caso exista
o caminho.
1.
Dado um grafo, achar para cada Árvore de Distância (formada a partir
de um vértice desse grafo) em quantas arestas ela difere da Árvore
de Custo Mínimo (MCST).
OBS: O
algoritmo deve rodar em O(|V|(|V|+|E|) log(|E|)). Ou seja para cada vértice, rodar
o algoritmo Dijkstra como visto em sala de aula (usando a estrutura heap) e
comparar a Árvore de Custo Mínimo (a partir do primeiro vértice).
OBS: Mesma observação do problema 2.