FloydWarshal programação dinamica caderno resposta

CADERNO DE RESPOSTAS: FLOYD-WARSHALL - PROGRAMAÇÃO DINÂMICA E GULOSA

PONTA GROSSA
2014
1. ITENS GERAIS

i) Enunciado Formal do problema.

O algoritmo de Floyd-Warshall, desenvolvido por Bernard Roy, Stephen Warshall e Robert Floyd, tem como objetivo encontrar o menor caminho entre todos os pares de vértices de um grafo valorado.

ii) Identificação e explicação da subestrutura ótima do problema.

Seja V={1,2,...,n};
Seja {1,2,...,k} um subconjunto de vértices para algum k;
Para quaisquer i,j V considere todos os caminhos de i até k com nós internos em {1,2,...,k}.
Seja p o menor caminho entre os dois vértices quaisquer i,j V com vértices internos em {1,2,...,k}.
Caso 1: k não está em p todos os vértices internos estão em {1,2,...,k-1}, neste caso não há vértices intermediários entre i e j, como mostra a figura abaixo, não há vértices intermediários entre o caminho de 1 à 3.

Caso 2: k está em p. Então:

Onde p1 e p2 são menores caminhos contendo vértices internos em {1,2,...,k-1}, neste caso o vértice 2 é intermediário para chegar a três pelo menor caminho de 1 até 3.

2. ITENS ESPECÍFICOS PARA A SOLUÇÃO DE PROGRAMAÇÃO DINÂMICA

i) Apresentação e explicação da recorrência que calcula o custo ótimo de uma istância do problema.

Dado um grafo valorado, para cada par de vértices s, t o custo de um caminho mínimo de s a t, tem-se:
Custo[k][s][t] = menor custo de um caminho de s a t usando vértices internos em {0,1,2,...,k-1}

Recorrência:
Custo[0][s][t] = G → adjacente [s][t]
Custo[k][s][t] = min { Custo[k-1][s][t], Custo[k-1][s][k-1] + Custo[k-1][k-1][t]}

Exemplo:
Custo[1][1,2][6] = G → adjacente [2,3][3] = 9
Custo[1][1,3][10] = 10
Custo[k][s][t] = min { Custo[1][1,3][10], Custo[1][1,2][6] + Custo[2][2,3][3]}

ii) Apresentação e explicação da matriz solução: significado das linhas, colunas, dos elementos gravados nas