Teoria dos Grafos - Aula 6 - Caminhos Mínimos Pt

Prévia do material em texto

Caminho mínimo
Um nó para todos os outros Dijkstra
Bellman Ford
Todos os nés para todos os nós Floyd Warshall
Johnson
Suponha 2
ATEEI9
a C E
5
ITO A B C D E
O O td td td
1
IT Ii A B C D E
O 4 2 to to
1 A A
IT 2 A B C D E
O 3 2 6 7
1 C A c c
IT 3 A B C D E
O 3 2 5 6
1 C A B B
IT 4 A.FI F1 C A B 8
O 3 2 5 6
deus que visitou o heap A C B D E
Caminho mínimo A C B E
Algoritmo de Dijkstra s
FOR ALL w e V
Dia a no
Façodoisvetoresdetomann
PREVE a NULL V umpara a dirtparamid
DISTES O Distância da pazma
e outro para o vérticeaurar
raiz é zero
H QUEUE V
WHILE MF b
DELETEMIN H
FOR ALL EDGES u V E E
IF DISTA Distrai fãs
ISTO DISTIM d fluiu
PREVIU se
DECREASE key Hiv
Complexidade Ol leltlthlog.lv D quando
de Pin Caso usa uma Heap de Fibonacci
que não é o caso no
algoritmo acima
EmPython
Entrada matriz de distâncias usavam
U tenho 1
VIin False Cnt1
a ENone t Epoatrinf D n
Min 1J
Algoritmo de Floyd Warshall
FOR EACH VERTEX V
DEVIA O
FOR EACH EDGE m v
pu v law
FOR K FROM 1 to V
FOR i FROM 1 To v
FOR j FROM a TO V
IF City DESCRITO Js
itjs DC.sk eDESCI
Complexidade O wi