Todo

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (568 palavras )
  • Download(s) : 0
  • Publicado : 11 de outubro de 2012
Ler documento completo
Amostra do texto
Dijkstra
O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calculao custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de performance. Ele não garante, contudo, a exatidão da solução caso haja a presença dearcos com valores negativos.
Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando játiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto.

Bellman-Ford

O algoritmo de Bellman-Ford resolve o problema docaminho mais curto de unica origem para o
caso mais geral, no qual os pesos das arestas podem ser negativos. Dado um grafo orientado
ponderado G = (V, E) com origem em s e funcao peso w:E → R, oalgoritmo retorna FALSE
quando encontra um ciclo de peso negativo indicando que nao existe solucao, ou retorna TRUE
indicando que produziu os caminhos mais curtos e seus pesos. O algoritmo usa a tecnicado
relaxamento, diminuindo progressivamente a estimativa d[v] no peso de um caminho mais curto.

Floyd Warshall

O algoritmo de Floyd Warshall tem como objetivo calcular a menor distancia detodos os vértices do grafo para todos os demais, recebendo, para isso, uma matriz de adjacência representando o grafo.
Com ordem de complexidade cúbica assuma que para percorrer o caminho A -> Chaverá um caminho A -> B e B -> C, isto é, para qualquer par de vértice ‘ (i, j) E V ’, considera-se todos os caminhos de ‘ iaj ’ cujos vértices intermediários pertencem ao subconjunto ‘ 1,2, 3..., k, ‘ e ‘ p ‘ como o mais curto de todos eles.
Algoritmo de Boruvka
Cada iteração do algoritmo de Boruvka começa com uma floresta geradora F de G.  (No início da primeira iteração, cada...
tracking img