bell (1)

Prévia do material em texto

Bellman-Ford and Floyd-Warshall
Francisco das Chagas Gomes de Carvalho 10564831
1UNIVERSIDADE ESTADUAL DO PIAUI - UESPI
franciscoccarvalho@aluno.uespi.br
Resumo.
1. Introdução
O algoritmo de bellman ford tem como objetivo encontrar o menor caminho em um dí-
grafo de uma única origem. Embora faça o mesmo que o Algoritmo de Dijkstra ele possui
uma vantagem, trabalho com arestas com pesosnegativos! É mais simples e fácil de com-
preender em casos raros é mais rápido que o algoritmo de Dijkstra
Dado um gráfico ponderado não direcionado G Com N Vértices. A tarefa é en-
contrar o comprimento do caminho mais curto Dij entre cada par de vértices EuEJ. O
gráfico pode ter bordas de peso negativas, mas nenhum ciclo de peso negativo (para então
o caminho mais curto é indefinido). Este algoritmo também pode ser usado para detectar
a presença de ciclos negativos. O gráfico tem um ciclo negativo se no final do algoritmo,
a distância de um vértice V para si mesmo é negativo. Este algoritmo foi publicado si-
multaneamente em artigos de Robert Floyd e Stephen Warshall em 1962. No entanto,
em 1959, Bernard Roy publicou essencialmente o mesmo algoritmo, mas sua publicação
passou despercebida.
2. Aplicação
AplicaçãoAplicação em roteamento: Um exemplo de aplicação, uma variação do al-
goritmo de Bellman-Ford é usado em routing protocols(protocolos deroteamento), por
exemplo, o Routing Information Protocol(RIP).O algoritmo envolve um número de nós
(roteadores) dentro de um Sistema Autônomo, uma coleção de redes IP normalmente de
propriedade de um ISP. É composto das seguintes etapas:
– Cada nó calcula as distâncias entre si e todos os outros nós dentro do AS e
armazena essas informações como uma tabela.
– Cada nó envia sua tabela para todos os nós vizinhos.
– Quando um nó recebe tabelas de distância de seus vizinhos, ele calcula as rotas
mais curtas para todos os outros nós e atualiza sua própria tabela para refletir as alterações.
O algoritmo Floyd-Warshall pode ser usado para resolver os seguintes problemas,
entre outros:
– Caminho mínimo em grafos direcionados (algoritmo de Floyd).
– Fechamento transitivo em grafos direcionados (algoritmo Warshall). É a formu-
lação original do algoritmo Marshall. O grafo é um grafo não ponderado e representado
por uma matriz Booleana de adjacência. Então, a operação de adição é substituída pela
conjunção lógica (AND) e a operação secundária pela disjunção lógica (OR).
– Encontre uma expressão regular dada por uma linguagem regular aceita por um
autômato finito (algoritmo de Kleene).
– Inversão de matrizes de números reais (algoritmo de Gauss-Jordan).
– Rota ótima. Nesta aplicação é interessante encontrar o caminho do fluxo má-
ximo entre 2 vértices. Isso significa que em vez de obter o mínimo com o pseudocódigo
anterior, o máximo é obtido. Os pesos lasar representam as limitações de fluxo. Os pesos
das estradas representam gargalos; portanto, a operação de adição anterior é substituída
pela operação mínima.
– Verifica se um gráfico não direcionado é bipartido.
3. Funcionamento Bellman-Ford
Em sua estrutura básica Bellman-Ford é muito semelhante ao algoritmo de Dijkstra. O
algoritmo usa o relaxamento, diminuindo progressivamente uma estimativa d[v] no peso
de um caminho mais curto da origem s até cada vértice v V até alcançar o peso real de
caminho mais curto (s,v).
O algoritmos de Bellman-Ford simplesmente relaxa todas as bordas, e faz isso |V|
-1 vezes, onde |V| é o número de vértices no gráfico. As repetições permitem distâncias
mínimas com precisão propagar por todo o gráfico, uma vez que, na ausência de ciclos
negativos, o caminho mais curto só pode visitar cada nó no máximo uma vez. Ao contrário
da abordagem gulosa, que depende de certas premissas estruturais derivadas de pesos
positivos, essa abordagem direta se estende para o caso geral.
O algoritmo de Bellman-Ford recebe um grafo orientado (G,w) (possivelmente
com arestas de custo negativo) e um vértice origem s de G. Ele devolve um valor booleano:
FALSE se existe um ciclo negativo atingível a partir de s, ou TRUE e neste caso devolve
também uma Arvore de Caminhos Mínimos com raiz s.
passo 1: Comece com o gráfico ponderado.
Page ii of xvi
Passo 2: Escolha um vértice inicial e atribua valores de caminho infinito a todos
os outros vértices.
Passo 3: Visite cada borda e relaxe as distâncias do caminho se elas forem impre-
cisas.
Page iii of xvi
passo 4: Precisamos fazer isso V vezes porque no pior caso, o comprimento do
caminho de um vértice pode precisar ser reajustado V vezes.
Passo 5: Observe como o vértice no canto superior direito teve seu comprimento
de caminho ajustado.
Page iv of xvi
Passo 6: Depois de todos os vértices terem seus comprimentos de caminho, veri-
ficamos se um ciclo negativo está presente.
Page v of xvi
4. Funcionamento Floyd-Warshal
A ideia-chave do algoritmo é dividir o processo de encontrar o caminho mais curto entre
quaisquer dois vértices para várias fases incrementais.
Vamos numerar os vértices a partir de 1 para N. A matriz das distâncias é D[][].
Antes K-th fase (k=1... n), D[i][j] para quaisquer vértices EuEJ armazena o com-
primento do caminho mais curto entre o vértice Eu e vértice J, que contém apenas os
vértices 1,2,. . . . . ,k1 como vértices internos no caminho.
Em outras palavras, antes K-th fase o valor de D[i][j] é igual ao comprimento do
caminho mais curto do vértice Eu para o vértice J, se esse caminho é permitido entrar
apenas no vértice com números menores do que K (o início e o fim do caminho não são
restritos por esta propriedade).
É fácil garantir que esta propriedade se mantenha para a primeira fase. Para k=0,
podemos preencher matriz com D[i][j]=Wij se existe uma borda entre EuEJ com peso
WijED[i][j]= se não existe uma borda. Na prática será algum valor alto. Como veremos
mais tarde, este é um requisito para o algoritmo.
Suponha agora que estamos no K-th fase, e queremos calcular a matriz D[][] de
modo que ele atende aos requisitos para o (k+1)- fase. Temos que corrigir as distâncias
para alguns pares de vértices (i,j). Há dois casos fundamentalmente diferentes:
O caminho mais curto do vértice Eu para o vértice J com vértices internos do
conjunto 1,2,... ,k coincide com o caminho mais curto com vértices internos do conjunto
1,2,... ,k1.
Neste caso, D[i][j] não mudará durante a transição.
O caminho mais curto com vértices internos de 1,2,... ,k é mais curto.
Isso significa que o novo caminho mais curto passa pelo vértice K. Isso significa
que podemos dividir o caminho mais curto entre EuEJ em dois caminhos: o caminho entre
EuEK, e o caminho entre KEJ. É claro que ambos os caminhos só usam vértices internos
de 1,2,... ,k1 e são os caminhos mais curtos a esse respeito. Portanto, já calculamos os
comprimentos desses caminhos antes, e podemos calcular o comprimento do caminho
mais curto entre EuEJ Como D[i][k]+D[k][j].
Combinando esses dois casos, descobrimos que podemos recalcular o compri-
mento de todos os pares (i,j) no K-esta fase da seguinte forma:
DNovo[i][j]=min(D[i][j],D[i][k]+D[k][j])
Assim, todo o trabalho que é necessário no K-a fase é iterar sobre todos os pares
de vértices e recalcular o comprimento do caminho mais curto entre eles. Como resultado,
depois do N-th fase, o valor D[i][j] na matriz de distância é o comprimento do caminho
mais curto entre Eu E J, ou é se o caminho entre os vértices Eu E J não existe.
Uma última observação - não precisamos criar uma matriz de distância separada
DNovo[][] para armazenar temporariamente os caminhos mais curtos do K-fase, ou seja,
todas as alterações podem ser feitas diretamente na matriz D[][] em qualquer fase. Na
verdade, em qualquer K-esta fase estamos no máximo melhorando a distância de qualquer
caminho na matriz de distância, portanto não podemos piorar o comprimento do caminho
Page vi of xvi
mais curto para qualquer par de vértices que devem ser processados no (k+1)-th fase ou
posterior.
A complexidade do tempo deste algoritmo é, obviamente, O(N3).
5. AlgoritmoBellman-Ford
Ao contrário de muitos outros algoritmos gráficos, para o algoritmo Bellman-Ford, é mais
conveniente representar o gráfico usando uma única lista de todas as bordas (em vez de N
listas de bordas - bordas de cada vértice). Iniciamos a implementação com uma estrutura
edge para representar as bordas. A entrada para o algoritmo são números N, MLista e de
bordas e o vértice inicial V. Todos os vértices estão numerados 0 Para n1.
A implementação mais simples A constante INF denota o número "infinito"— ele
deve ser selecionado de tal forma que seja maior do que todos os comprimentos possíveis
do caminho.
A verificação só é necessária se o gráfico contiver bordas de peso negativas: ne-
nhuma verificação resultaria em relaxamento dos vértices para os quais os caminhos ainda
não encontraram, e distância incorreta, do tipo if (d[e[j].a] < INF)1, 2 etc. apareceria.
Uma melhor implementação Este algoritmo pode ser um pouco acelerado: muitas
vezes já odiamos a resposta em algumas fases e nenhum trabalho útil é feito em fases
remanescentes, apenas um desperdício visitando todas as bordas. Então, vamos manter a
bandeira, para dizer se algo mudou na fase atual ou não, e se alguma fase, nada mudou, o
algoritmo pode ser parado. (Essa otimização não melhora o comportamento assintotótico,
ou seja, alguns gráficos ainda precisarão de todos n1 fases, mas acelera significativamente
o comportamento do algoritmo "em média", ou seja, em gráficos aleatórios.)
Com essa otimização, geralmente é desnecessário restringir manualmente o nú-
mero de fases do algoritmo para n1 — o algoritmo vai parar após o número desejado de
fases.
Page vii of xvi
Caminho de recuperação Vamos agora considerar como modificar o algoritmo
para que ele não só encontre o comprimento de caminhos mais curtos, mas também per-
mita reconstruir os caminhos mais curtos.
Para isso, vamos criar outra matriz p[0... n1], onde para cada vértice armazenamos
seu "antecessor", ou seja, o penúltimo vértice no caminho mais curto que o leva. Na
verdade, o caminho mais curto para qualquer vértice Um é um caminho mais curto para
algum vértice p[a], ao qual adicionamos Um no final do caminho.
Note que o algoritmo funciona na mesma lógica: ele assume que a menor distância
para um vértice já é calculada, e, tenta melhorar a menor distância para outros vértices
a partir desse vértice. Portanto, no momento da melhoria só precisamos lembrar P[], ou
seja, o vértice do qual essa melhoria ocorreu.
A seguir está uma implementação do Bellman-Ford com a recuperação do cami-
nho mais curto para um determinado nó T:
Page viii of xvi
Aqui a partir do vértice T, passamos pelos antecessores até chegarmos ao vértice
inicial sem antecessor, e armazenar todos os vértices no caminho da lista path. Esta lista
é um caminho mais curto de V Para T, mas em ordem inversa, então chamamos reverse()
função mais path e, em seguida, sair o caminho.
A prova do algoritmo Primeiro, note que para todos os vértices inalcançáveis U o
algoritmo funcionará corretamente, o rótulo D[U] permanecerá igual ao infinito (porque
o algoritmo Bellman-Ford encontrará algum caminho para todos os vértices alcançáveis
desde o vértice inicial V, e relaxamento para todos os outros vértices restantes nunca
acontecerá).
Vamos agora provar a seguinte afirmação: Após a execução de Euth fase, o algo-
ritmo Bellman-Ford encontra corretamente todos os caminhos mais curtos cujo número
de bordas não excede Eu.
Em outras palavras, para qualquer vértice Um vamos denotar o K número de bor-
das no caminho mais curto para ele (se houver vários desses caminhos, você pode tomar
qualquer). De acordo com esta afirmação, o algoritmo garante que depois Kth fase o
caminho mais curto para vértice Um será encontrado.
Prova: Considere um vértice arbitrário Um para o qual há um caminho a partir
do vértice inicial V, e considere um caminho mais curto para ele (P0=v,P1,... ,PK=Um).
Antes da primeira fase, o caminho mais curto para o vértice P0=V foi encontrado correta-
mente. Durante a primeira fase, a borda (P0,P1) foi verificado pelo algoritmo e, portanto,
a distância para o vértice P1 foi corretamente calculado após a primeira fase. Repetindo
Page ix of xvi
esta declaração K vezes, vemos que depois Kth fase a distância para o vértice PK=Um é
calculado corretamente, o que queríamos provar.
A última coisa a notar é que qualquer caminho mais curto não pode ter mais do
que n1 Bordas. Portanto, o algoritmo vai suficientemente até o (n1)th Fase. Depois disso,
é garantido que nenhum relaxamento irá melhorar a distância para algum vértice.
O caso de um ciclo negativo Em todos os lugares acima consideramos que não há
ciclo negativo no gráfico (precisamente, estamos interessados em um ciclo negativo que
é alcançável a partir do vértice inicial V, e, para um ciclo inalcançável nada no algoritmo
acima muda). Na presença de um ciclo negativo, há outras complicações associadas ao
fato de que as distâncias a todos os vértices deste ciclo, bem como as distâncias para os
vértices alcançáveis a partir deste ciclo não são definidas — elas devem ser iguais a menos
infinito ().
É fácil ver que o algoritmo Bellman-Ford pode fazer infinitamente o relaxamento
entre todos os vértices deste ciclo e os vértices alcançáveis a partir dele. Portanto, se
você não limitar o número de fases para n1, o algoritmo será executado indefinidamente,
constantemente melhorando a distância desses vértices.
Portanto, obtemos o critério para a presença de um ciclo de pesos negativos alcan-
çáveis para vértice fonte V: depois (n1)th fase, se executarmos algoritmo para mais uma
fase, e ele realiza pelo menos mais um relaxamento, então o gráfico contém um ciclo de
peso negativo que é alcançável a partir de V; caso contrário, tal ciclo não existe.
Além disso, se tal ciclo for encontrado, o algoritmo Bellman-Ford pode ser mo-
dificado para que ele recupere este ciclo como uma sequência de vértices contidos nele.
Para isso, basta lembrar o último vértice X para o qual houve um relaxamento em NTH
Fase. Este vértice estará em um ciclo de peso negativo, ou é alcançável a partir dele.
Para obter os vértices que são garantidos para mentir em um ciclo negativo, a partir do
vértice X, passar para os antecessores N Vezes. Por isso, vamos pegar o vértice Y, ou
seja, o vértice no ciclo mais antigo alcançável da fonte. Temos que ir deste vértice, atra-
vés dos antecessores, até voltarmos ao mesmo vértice Y (e isso vai acontecer, porque o
relaxamento em um ciclo de peso negativo ocorre de forma circular).
Page x of xvi
Devido à presença de um ciclo negativo, para N iterações do algoritmo, as distân-
cias podem ir longe na faixa negativa (para números negativos da ordem de –nmW Onde
W é o valor absoluto máximo de qualquer peso no gráfico). Assim, no código, adotamos
medidas adicionais contra o transbordamento de inteiros da seguinte forma:
A implementação acima procura um ciclo negativo acessível a partir de algum
vértice inicial V; no entanto, o algoritmo pode ser modificado para apenas procurar qual-
quer ciclo negativo no gráfico. Para isso precisamos colocar toda a distância D[Eu] a zero
e não ao infinito — como se estivéssemos procurando o caminho mais curto de todos os
vértices simultaneamente; a validade da detecção de um ciclo negativo não é afetada.
Algoritmo mais curto do caminho mais rápido (SPFA) SPFA é uma melhoria do
algoritmo Bellman-Ford que se aproveita do fato de que nem todas as tentativas de rela-
xamento funcionarão. A ideia principal é criar uma fila contendo apenas os vértices que
estavam relaxados, mas que ainda poderiam relaxar ainda mais seus vizinhos. E sempre
que você pode relaxar algum vizinho, você deve colocá-lo na fila. Este algoritmo também
pode ser usado para detectar ciclos negativos como o Bellman-Ford.
Page xi of xvi
O pior caso deste algoritmo é igual ao O(nm) do Bellman-Ford, mas na prática
ele funciona muito mais rápido e alguns as pessoas afirmam que ele funciona mesmo em
O(m) em média. No entanto, tenha cuidado, poiseste algoritmo é determinista e é fácil
criar contra examples que fazem o algoritmo funcionar O(nm).
Há algum cuidado a ser tomado na implementação, como o fato de que o algoritmo
continua para sempre se houver um ciclo negativo. Para evitar isso, é possível criar um
contador que armazena quantas vezes um vértice foi relaxado e parar o algoritmo assim
que algum vértice ficou relaxado para o N- é a vez. Note, também não há razão para
colocar um vértice na fila se ele já estiver dentro.
6. Algoritmo Floyd-Warshall
Deixe D[][] é uma matriz 2D de tamanho n×n, que é preenchido de acordo com o 0-th
fase como explicado anteriormente. Também vamos definir D[i][i]=0 para qualquer Eu
no 0- fase.
Em seguida, o algoritmo é implementado da seguinte forma:
Page xii of xvi
Presume-se que se não houver borda entre dois vértices Eu E J, em seguida, a
matriz em D[i][j] contém um número grande (grande o suficiente para que seja maior do
que o comprimento de qualquer caminho neste gráfico). Então essa borda sempre será
pouco rentável de tomar, e o algoritmo funcionará corretamente.
No entanto, se houver bordas de peso negativas no gráfico, medidas especiais de-
vem ser tomadas. Caso contrário, os valores resultantes na matriz podem ser da forma 1,
2, etc., o que, é claro, ainda indica que entre os respectivos vértices não existe um cami-
nho. Portanto, se o gráfico tem bordas de peso negativas, é melhor escrever o algoritmo
Floyd-Warshall da seguinte maneira, para que ele não realize transições usando caminhos
que não existem.
Recuperando a sequência de vértices no caminho mais curto É fácil manter in-
formações adicionais com as quais será possível recuperar o caminho mais curto entre
qualquer dois vértices na forma de uma sequência de vértices.
Para isso, além da matriz de distância D[][], uma matriz de ancestrais P[][] deve
ser mantido, o que conterá o número da fase em que a menor distância entre dois vértices
foi modificada pela última vez. É claro que o número da fase nada mais é do que um
vértice no meio do caminho mais curto desejado. Agora só precisamos encontrar o cami-
nho mais curto entre os vértices Eu E p[i][j], e entre p[i][j] E J. Isso leva a um simples
algoritmo de reconstrução recursiva do caminho mais curto.
O caso dos pesos reais Se os pesos das bordas não são inteiros, mas reais, é ne-
cessário levar em conta os erros, que ocorrem ao trabalhar com tipos de flutuação, em
conta.
O algoritmo floyd-warshall tem o efeito desagradável, que os erros se acumulam
muito rapidamente. Na verdade, se houver um erro na primeira fase de , este erro pode
se propagar para a segunda iteração como 2, para a terceira iteração como 4, e assim por
diante.
Para evitar isso, o algoritmo pode ser modificado para pegar o erro (EPS = ) em
conta usando a seguinte comparação:
Page xiii of xvi
O caso dos ciclos negativos Formalmente, o algoritmo floyd-warshall não se aplica
a gráficos contendo ciclos de peso negativos. Mas para todos os pares de vértices Eu E
J para o qual não existe um caminho começando em Eu, visitando um ciclo negativo, e
terminar em J, o algoritmo ainda funcionará corretamente.
Para o par de vértices para os quais a resposta não existe (devido à presença de
um ciclo negativo no caminho entre eles), o algoritmo floyd armazenará qualquer número
(talvez altamente negativo, mas não necessariamente) na matriz de distância. No entanto,
é possível melhorar o algoritmo Floyd-Warshall, de modo que ele trata cuidadosamente
tais pares de vértices, e os produz, por exemplo, como INF.
Isso pode ser feito da seguinte maneira: vamos executar o algoritmo floyd-warshall
usual para um determinado gráfico. Em seguida, um caminho mais curto entre os vértices
Eu E J não existe, se e somente se, há um vértice T que é alcançável a partir de Eu e
também de J, para o qual D[][t]<0 .
Além disso, ao usar o algoritmo Floyd-Warshall para gráficos com ciclos nega-
tivos, devemos ter em mente que situações podem surgir em que distâncias podem ficar
exponencialmente rápidas no negativo. Portanto, o transbordamento inteiro deve ser ma-
nuseado limitando a distância mínima por algum valor (por exemplo. INF).
7. Floyd-Warshall vs Dijkstra
O Algoritmo de Dijkstra é um exemplo de um algoritmo SSSP mais curto ou de uma
única fonte, ou seja, dado um vertex fonte que encontra o caminho mais curto da fonte
para todos os outros vértices. Floyd Warshall Algorithm é um exemplo de algoritmo de
caminho mais curto de todos os pares, o que significa que ele calcula o caminho mais
curto entre todos os nós.
Complexidade temporal do Algoritmo de Dijkstra: O(E log V) Complexidade do
tempo de Floyd Warshall: O(V3)
Podemos usar o algoritmo de caminho mais curto da Dijkstra para encontrar todos
os caminhos mais curtos do par executando-o para cada vértice. Mas a complexidade do
tempo disso seria O(VE Log V) que pode ir (V3 Log V) na pior das hipóteses.
Outro importante diferencial entre os algoritmos é o seu trabalho em direção a
sistemas distribuídos. Ao contrário do algoritmo de Dijkstra, Floyd Warshall pode ser
implementado em um sistema distribuído, tornando-o adequado para estruturas de dados
como Gráfico de Gráficos (Usado em Mapas).
Por fim, Floyd Warshall trabalha para borda negativa, mas sem ciclo negativo,enquanto
o algoritmo de Dijkstra não funciona para bordas negativas.
8. Bellman-Ford vs Dijkstra
Algoritmo Bellman-ford:
O Algoritmo de Bellman Ford funciona quando há borda de peso negativo, ele
também detecta o ciclo de peso negativo.
O resultado contém os vértices que contém as informações sobre os outros vértices
a que estão conectados.
Page xiv of xvi
Pode ser facilmente implementado de forma distribuída.
É mais demorado do que o algoritmo de Dijkstra. Sua complexidade temporal é
O(VE).
A abordagem de programação dinâmica é tomada para implementar o algoritmo.
Algoritmo de Dijkstra:
O Algoritmo de Dijkstra não funciona quando há vantagem de peso negativo.
O resultado contém os vértices contendo informações inteiras sobre a rede, não
apenas os vértices a que estão conectados.
Não pode ser implementado facilmente de forma distribuída.
É menos demorado. A complexidade do tempo é O(E logV).
Abordagem gananciosa é tomada para implementar o algoritmo.
9. Implementação
Implementação em Bellman-Ford
https://github.com/fr4ncisco123/bellman
Referências
Bellman, Richard(1958), "Em um problema de roteamento",Trimestral de Mate-
mática Aplicada16:87-90,MR0102435.
Ford, LR, Jr.;Fulkerson, DR(1962),Fluxos em Redes,Princeton University Press.
Cormen, Thomas H.;Leiserson, Charles E.,Rivest, Ronald L..Introduction to Al-
gorithms.MIT PresseMcGraw-Hill., Segunda edição.MIT Press e McGraw-Hill, 2001.ISBN
0-262-03293-7.Artigo 24.1: O algoritmo de Bellman-Ford, pp 588-592.Problema 24-1,
pp 614-615.
http://www.ime.usp.br/ pf/algoritmosparagrafos/aulas/bellman-ford.html.
http://www.cp-algorithms.com/graph/all-pair-shortest-path-floydwarshall.html.
http://www.programiz.com/dsa/bellman-ford-algorithm.
http://www.cp-algorithms.com/graph/bellmanford.htmltoc-tgt-0.
https://pdfcoffee.com/algoritmo-de-floyd-warshall-3-pdf-free.html
https://www.programiz.com/dsa/bellman-ford-algorithm
https://www.youtube.com/watch?v=vEztwiTELWs
https://www.geeksforgeeks.org/comparison-dijkstras-floyd-warshall-algorithms/
https://www.geeksforgeeks.org/what-are-the-differences-between-bellman-fords-and-
dijkstras-algorithms/
http://www.joshuarobinson.net/docs/fwarsh.html
http://julmis.julmajanne.com/index.php/FloydWarshall
http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortestpath/shortestpath.html
Page xv of xvi
https://github.com/fr4ncisco123/bellman
http://dx.doi.org/10.1145/367766.368168
http://dx.doi.org/10.1145/321105.321107
http://www.tu.tv/videos/algoritmo-de-floyd[7]http://videopractico.com/vp/?p=3
Page xvi of xvi
	Introdução
	Aplicação
	Funcionamento Bellman-Ford
	Funcionamento Floyd-Warshal
	Algoritmo Bellman-Ford
	Algoritmo Floyd-Warshall
	Floyd-Warshall vs Dijkstra
	Bellman-Ford vs Dijkstra
	Implementação