Algoritmo de Dijkstra

Otimização em Redes
Algoritmo de Dijkstra

Ana Carolina Martins Rosa (UTFPR) [e-mail] Flavia Andrea Harms (UTFPR) [e-mail]
Ian Profeta da Rosa (UTFPR) [e-mail]

Resumo

A otimização em redes busca minimizar uma função de custo que depende do fluxo que passa pelos arcos de uma rede. A partir da estrutura de rede, consegue-se criar algoritmos especializados, com grandes vantagens computacionais, que ajudam na minimização desses custos.
Este trabalho focará na apresentação do Algoritmo de Dijkstra, mostrando sua resolução manualmente e depois em um protótipo, realizado através da linguagem C.
Este algoritmo consegue solucionar problemas de caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo. É dito um algoritmo guloso, pois toma a decisão que lhe parece ótima no momento, porém, mesmo assim, é considerado eficiente.
Palavra chave: Algoritmo de Dijkstra, resolução manual, implementação de um protótipo.

Abstract

The network optimization seeks to minimize a cost function which depends on the flow passing through arcs of the network. From the network structure, it is possible to create specialized algorithms, large computational advantages that help in minimizing these costs.
This work will focus on the presentation of Dijkstra's algorithm, showing its resolution manually and then a prototype, conducted by C language
This algorithm can solve problems of shortest path in a directed graph or undirected edges with non-negative weight. It is called a greedy algorithm, because the decision takes that sound great right now, but even so, it is considered efficient.
Keyword: Dijkstra's algorithm, manual resolution, implementation of a prototype.

1. Introdução

Otimizar, é a ação mais pretendida no cotidiano das pessoas hoje em dia, seja em questão de tempo ou dinheiro. Quem nunca errou alguma rota a fim de chegar no lugar pretendido e acabou gastando mais