Algoritmo de dijkstra

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 a way 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 the student. 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. Quando o 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 uma