1. Considere o algoritmo de Dijkstra para encontrar o caminho mais curto entre um vértice fonte e os demais vértices de um grafo orientado G=(V,E) onde a distância associada a um arco e Î E é dada por l_e = l_vw onde v e w são o vértice de partida e de chegada do arco e, respectivamente. (As complexidades devem ser obtidas em função de n=|V| e m=|E|).
   
   Algoritmo Dijkstra (s - fonte)
   • Passo 0: Inicialização
     
     Seja S o conjunto de vértices com caminho mais curto a partir de s determinado, e S seu complemento (S = V - S).
     
     S ¬ Ø
     
     d(i) ¬ +¥ " i Î V;
     
     d(s) ¬ 0; pred(s) ¬ 0;
     
     
   • Passo 1: Iteração
     • Enquanto S Ì V faça
       
       
       • 1.1 Encontre v Î S t.q. d(v) = min_{w Î S} d(w)
         
         
       • 1.2 S ¬ S È { v }; S ¬ S \ { v };
         
         
       • 1.3 Para todo w Î G⁺ (v)
         
         Se d(v) + l_vw < d(w)
         
         então d(w) ¬ d(v) + l_vw; pred(w) ¬ v;
   
   Responda aos itens abaixo:
   1. Considere que o passo 1.1 é realizado através do uso de um vetor que armazena os valores d(i), i=1,...,n. Qual a complexidade desta implementação do algoritmo de Dijkstra ?
   2. Qual a complexidade global do passo 1.1 ? E do item 1.3 ?
   3. A implementação que utiliza uma d-Heap para armazenar d(i) faz uso das operaoeremove-topo(H) no passo 1.1 e reduz-chave(H, posicao(v), novo-valor) no passo 1.3. Reescreva estes passos utilizando estas operaoee analise a complexidade global do algoritmo.
   4. Considere agora que todas as distâncias l_vw são inteiros e que C= max_{(v,w) Î E} l_vw (qual a maior distância possível em um caminho ?). Observe que a distância d(v) do vértice selecionado no passo 1.1 a cada iteração é maior ou igual à do vértice selecionado na iteração anterior. Considere que buckets (ou caixas) são criadas para os valores de 0 a nC. Cada bucket utiliza uma lista duplamente encadeada para armazenar os vértices v tais que d(v) tem o valor correspondente ao bucket. Um vetor (d) é utilizado para indicar em que bucket está armazenado.
      1. Escreva os passos 1.1 e 1.3 utilizando a estrutura descrita acima.
      2. Analise a complexidade deste algoritmo. Qual seria a complexidade deste algoritmo quando as distâncias são dadas pelo número de arestas no caminho ?
   
   
2. Considere o problema de encontrar o caminho-mais-curto entre todos os pares de vértices onde os arcos do grafo orientado G=(V,E) podem assumir valores negativos.
   1. Proponha um algoritmo para determinar se o grafo possui ciclo negativo. Analise sua complexidade.
   2. Proponha um algoritmo que, nos casos em que um ou mais ciclos negativos estão presentes em G, indique os pares de vértices que possuem caminhos-mais-curtos entre eles em G, ou seja cmc's que não passam pelos ciclos negativos.
   
   
3. (C,L & R, 1990, ex. cap 24-1 ou C, L, R & S, 2001, ex. cap 23-1 ) ``Second best minimum spanning tree''
   
   
4. (C,L & R, 1990, ex. cap 25-1 ou C, L, R & S, 2001, ex. cap 24-1 ) ``Yen's improvement to Bellman-Ford''
   
   
5. (C,L & R, 1990, ex. cap 25-3 ou C, L, R & S, 2001, ex. cap 24-3 ) ``Arbitrage''
   
   
6. (C,L & R, 1990, ex. cap 27-5 ou C, L, R & S, 2001, ex. cap 26-5 ) ``Maximum flow by scaling''
   
   
7. (C,L & R, 1990, ex. cap 25-4 ou C, L, R & S, 2001, ex. cap 24-4 ) ``Gabow's scaling algorithm...''

This document was translated from L^AT_EX by H^EV^EA.