Algoritmo de Prim e Floyd warshall

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Análise de Algoritmos
1
Algoritmo Guloso - Prim
2
Algoritmo Guloso - Prim
3
Algoritmo Guloso - Prim
4
Algoritmo Guloso - Prim
5
Algoritmo Guloso - Prim
6
Algoritmo Guloso - Prim
7
Algoritmo Guloso - Prim
8
Algoritmo Guloso - Prim
9
Algoritmo Guloso - Prim
10
Algoritmo Guloso - Prim
11
A: Número de arestas
V: Número de vértices
	Complexidade: O(|A|log|V|)
Programação Dinâmica - Floyd-Warshall
Sejam:
d representa a matriz de adjacência
1 ≤ i, j ,k ≤ n
Onde n representa o número de vértices do grafo
Recorrência:
	d[i,j] = min{d[i,j], d[i, k]+d[k,j]}
12
Programação Dinâmica - Floyd-Warshall
13
Programação Dinâmica - Floyd-Warshall
14
Programação Dinâmica - Floyd-Warshall
15
Programação Dinâmica - Floyd-Warshall
16
Programação Dinâmica - Floyd-Warshall
17
Programação Dinâmica - Floyd-Warshall
18
Seja:
	V o Número de vértices.
Complexidade: Θ(|V³|)
Problemas:
Estradas Escuras (Dark Roads)
https://www.urionlinejudge.com.br/judge/pt/problems/view/1152
https://www.informatik.uni-ulm.de/acm/Locals/2009/html/dark.html
Problema D - As Viagens de Sander
http://maratona.wp.facom.ufms.br/2017/07/19/solucoes-dos-problemas-desafio-facom-2017-2/
19
Bibliografia:
http://noic.com.br/informatica/curso-noic-de-informatica/aula-17-grafos-v-mst-arvore-geradora-minima/
https://www.ime.usp.br/~coelho/mac328/pf/floyd.html
20