Ccb08b12c101be

PESQUISA OPERACIONAL

MODELOS DE REDE
(Cont.)

Prof: Anderson Góes
[e-mail]

PESQUISA OPERACIONAL
Algoritmo de Floyd-Warshall
O algoritmo de Floyd-Warshall recebe como entrada uma matriz de adjacência que representa um grafo (V,E) orientado e valorado.
O valor de um caminho entre dois vértices é a soma dos valores de todas as arestas ao longo desse caminho. As arestas E do grafo podem ter valores negativos, mas o grafo não pode conter nenhum ciclo de valor negativo. O algoritmo calcula, para cada par de vértices, o menor de todos os caminhos entre os vértices. Por exemplo, o caminho de menor custo. Sua ordem de complexidade é θ(|V|3).

PESQUISA OPERACIONAL
Algoritmo de Floyd-Warshall
O algoritmo se baseia nos passos abaixo:
Assumindo que os vértices de um grafo orientado G são
V=1,2,3,…,n, considere um subconjunto 1,2,3…,k;
Para qualquer par de vértices (i,j) em V, considere todos os caminhos de i a j cujos vértices intermediários pertencem ao subconjunto 1,2,3…,k, e p como o mais curto de todos eles;
O algoritmo explora um relacionamento entre o caminho p e os caminhos mais curtos de i a j com todos os vértices intermediários em 1,2,3…,k−1;
O relacionamento depende de k ser ou não um vértice intermediário do caminho p.

PESQUISA OPERACIONAL
Implementação

PESQUISA OPERACIONAL
Exemplo

PESQUISA OPERACIONAL
Exemplo

PESQUISA OPERACIONAL
Exemplo

PESQUISA OPERACIONAL
Algoritmo de Bellman Ford

O algoritmo está divido em três etapas (inicialização, relaxamento e verificação de ciclos negativos). A primeira, a inicialização, é responsável por padronizar as distâncias antes do inicio da resolução. O relaxamento fica responsável pelo cálculo do caminho mínimo e a última etapa se responsabiliza em verificar se é possível ou não calcular o caminho mínimo partindo do princípio que não se pode ter um ciclo negativo. PESQUISA OPERACIONAL
Algoritmo de Bellman Ford

A existência e cálculo do caminho mais curto são