ENGENHARIA DE CONTROLE E AUTOMOÇÃO

[pic 1]

FACULDADE ANHANGUERA DE MATÃO

Engenharia de Controle e Automação

10ª série

Matão – SP

27 de setembro de 2016

[pic 2]

Trabalho acadêmico apresentado como exigência da disciplina Inteligência Artificial, do curso de Engenharia de Controle e Automação, da Faculdade Anhanguera de Matão.

Prof. Henrique Geraldo de Moraes

                                                 10ª série

Nome	RA
Alex Martins Galan André Luiz da Silva Vasconcelio Miranda Junior	4662899244 4236810596 3715672796

Matão – SP

27 de setembro de 2016

ATPS

Algoritmo de Dijkstra

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices.

Alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho entre A e F?

– Construir a árvore de menor comprimento total entre todos os nós de um grafo.

– Encontrar o caminho de menor comprimento total entre dois determinados nós de um grafo.

        Nesta Atividades foi apresentado um problema prático, onde será aplicado o algoritmo de Dijkstra para a resolução desse problema. 

Aplicação Prática terá como objetivo, um controlador viajar da cidade inicial ARAD até a cidade final de BUCHAREST, DENTRO do menor caminho.

Lembrando que o Algoritmo de Dijkstra, é a busca sem o conhecimento do trajeto total, e tem como finalidade encontrar o menor caminho possível.

Sendo assim, segue a figura com os estados, onde os serão tratados em Quilômetros –KM, concordando   ponto a ponto, onde o algoritmo Dijkstra soma do ponto inicial, aos pontos mais próximos um passo de cada vez, assim este ponto mais próximo encontrado será nova referência e terá o acumulativos de distâncias já percorridas, decorrendo passo a passo.

---

Logo temos,

[pic 3]

Calculando o Algoritmo de Dijkstra:

Cidades	Passo 1	Passo 2	Passo 3	Passo 4	Passo 5	Passo 6
ARAD	0,ARAD	X	X	X	X	X
TIMISOARA	118,ARAD	∞	∞	∞	∞	∞
ZERIND	75,ARAD	75,ARAD	X	X	X	X
ORADEA	∞	146,ZERIND	146,ZERIND	X	X	X
SIBIU	140,ARAD	∞	297,ORADEA	297,ORADEA	X	X
LUGOJ	∞	∞	∞	∞	∞	∞
FAGARAS	∞	∞	∞	387,SIBIU	∞	∞
MEHADIA	∞	∞	∞	∞	∞	∞
RIMNICU VILCEA	∞	∞	∞	377,SIBIU	377,SIBIU	X
PITESTI	∞	∞	∞	∞	474, RIMNICU VILCEA	474, RIMNICU VILCEA
GIURGIU	∞	∞	∞	∞	∞	∞
BUCHAREST	∞	∞	∞	∞	∞	575, PIRESTI