Algoritmo de dijkstra

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2145 palavras )
  • Download(s) : 0
  • Publicado : 9 de dezembro de 2012
Ler documento completo
Amostra do texto
ALGORITMO DE DIJKSTRA: APOIO DIDÁTICO E MULTIDISCIPLINAR NA IMPLEMENTAÇÃO, SIMULAÇÃO E UTILIZAÇÃO COMPUTACIONAL
Edson A. R. Barros 1, Sergio V. D. Pamboukian 2, Lincoln C. Zamboni 3
Abstract  Since the decade of 70, the programming have showing itself as an essential and indispensable tool for students, engineers and researchers. It is fact that the programming languages developed from such away to allow the conception of classes of objects and the modeling of the techno-scientific problems in a simple way. In the Escola de Engenharia of the Universidade Presbiteriana Mackenzie, that it is commemorating their 110 years of existence, grows several interconnected projects that use the programming as tool not only of search of the solution, but also didacticism and practice for thestudent. This is the case of use of the Algorithm of Dijkstra that, with its simplicity, reveals a didactic support in the implementation of classes, simulation and reuse in the most several engineering applications. Index Terms  programming languages, programming with classes, simulation, reuse. Dijkstra, caminho mínimo entre dois vértices. Ele é desenvolvido em uma árvore de caminhos mínimos. Quandoo grafo não for simples, então se procura transformá-lo em um grafo simples eliminando seus laços e eventuais arestas múltiplas deixando apenas a com o peso menor. A complexidade do Algoritmo de Dijkstra é O(n2), onde n é a quantidade de vértices do grafo [1].

O ALGORITMO
Para entender os passos do Algoritmo de Dijkstra se deve seguir minuciosamente o Fluxograma apresentado na Figura 3.Inicialmente os vértices do grafo em estudo devem ser numerados, o que resulta em uma matriz de vínculos e pesos que pode ser usada como base para se desenvolver a lógica do programa. Na Figura 1 se apresenta um grafo ilustrativo para melhor compreensão do algoritmo e na Figura 2 sua respectiva matriz de vínculos e pesos [1][2].

Resumo  Desde a década de 70, a programação vem se mostrando como umaferramenta essencial e indispensável para estudantes, engenheiros e pesquisadores. É fato que as linguagens de programação evoluíram de tal forma a permitir a concepção de classes de objetos e a modelagem dos problemas técnico-científicos de forma simples, clara e objetiva. Na Escola de Engenharia da Universidade Presbiteriana Mackenzie, em seus 110 anos de existência, desenvolve-se diversosprojetos multidisciplinares que utilizam a programação como ferramenta não só de busca da solução, mas também no reúso desta solução em outros projetos. Este é o caso de uso do Algoritmo de Dijkstra que, com sua simplicidade, revela seu apoio didático e multidisciplinar na implementação de classes, simulação e reúso nas mais diversas aplicações de engenharia. Palavras chaves  linguagens deprogramação, Dijkstra, programação com classes, simulação, reúso.

FIGURA. 1
GRAFO ILUSTRATIVO COM 11 VÉRTICES.

INTRODUÇÃO
O Algoritmo de Dijkstra foi desenvolvido em 1959 por Edsger Wybe Dijkstra, de onde vem a origem do nome. Este algoritmo se aplica em grafos simples para determinar o

O passo seguinte é definir respectivamente o vértice origem (u0) e o vértice destino (uf) na matriz de dados. Paraa atual demonstração, a origem é o vértice 4 (u0=4) e o destino é o vértice 8 (uf=8). Na seqüência criam-se dois conjuntos de vértices, o M dos vértices marcados, e o D dos vértices desmarcados. A marcação pode ser feita por meio de um vetor com dados do tipo booleano (bool), verdadeiro (true) ou falso (false), dessa

1 Edson de Almeida Rego Barros, Escola de Engenharia, UniversidadePresbiteriana Mackenzie, Rua da Consolação, 930, 01302-907, Consolação, São Paulo, SP, Brazil, prof_edson@mackenzie.com.br 2 Sergio Vicente Denser Pamboukian, Escola de Engenharia, Universidade Presbiteriana Mackenzie, Rua da Consolação, 930, 01302-907, Consolação, São Paulo, SP, Brazil, sergiop@mackenzie.com.br 3 Lincoln César Zamboni, Escola de Engenharia, Universidade Presbiteriana Mackenzie, Rua da...
tracking img