Os Algoritmos em Grafos

Algoritmos em Grafos - Atividade #3

Problema 24-3 do Livro Cormen

A arbitragem é a utilização de discrepâncias em taxas de câmbio para transformar uma unidade de uma moeda em mais de uma unidade da mesma moeda. Por exemplo, suponha que 1 dólar americano compre 49 rupias indianas. Uma rupia indiana compra dois ienes japoneses, e um iene japonês compra 0,0107 dólar americano. Então, convertendo moedas, um comerciante pode começar com um dólar americano e comprar

49 x 2 x 0,0107 = 1,0486 dólar americano, obtendo assim um lucro de 4,86%.

Suponha que recebemos n moedas c1, c2, ..., cn e uma tabela R n × n de taxas de câmbio, tal que uma unidade da moeda ci compre R[i, j] unidades da moeda cj

1. Dê um algoritmo eficiente para determinar se existe ou não uma sequência de moedas ⟨ci 1, ci 2, ...,cik⟩ tal  que R[i1,i2]xR[i2,i3]x...xR[ik-1,ik] x R[ik,i1]

Pode-se determinar se existe ou não uma sequência de moedas através de algoritmos de caminhos mínimos.

Utilizando o algoritmo de Floyd-Warshall por exemplo, sendo os vértices as moedas (ci 1, ci 2, ...,cik) e as arestas com pesos R[i, j] (taxas de câmbio)  ele calculará os caminhos mais curtos entre todos os pares de vértices.

L: Matriz que armazena os caminhos mais curtos entre os vértices;

Inicialmente, L é inicializada com os pesos dos arcos do grafo (rij);

Caso não haja arco entre dois vértices i e j, rij = ∞.

lij : elemento da matriz L na linha i e coluna j.

Entrada: Grafo G = (V , E) e matriz de pesos R={rij} para os arcos {i, j}

1   -  L ← D;//Inicializa os elementos da matriz L

2   -  para k ← 1 até n faça

3   -         para i ← 1 até n faça

4   -                 para j ← 1 até n faça

5   -                         se lij > lik + lkj então

6   -                                 lij ← lik + lkj ;

7   -                         fim

8   -                  fim

9   -          fim

10 - fim

Caso exista um caminho mínimo, ele será a sequência de moedas existentes.

1. Analise o tempo de execução do seu algoritmo.

Para a execução do algoritmo de Floyd-Warshall o tempo será igual a O (n3).

...