ESTUDO DO DESEMPENHO DO ALGORITMO DE DIJKSTRA NOS ROTEADORES

ESTUDO DO DESEMPENHO DO ALGORITMO DE DIJKSTRA NOS ROTEADORES
Autor: Moisés Alexandre Lustosa da Silva1
Co-autor: Prof. Dr. Fábio Hernandes2
RESUMO
O problema de caminho mínimo é um dos mais estudados da teoria dos grafos, visto que aparece em muitas aplicações, tais como: computação, telecomunicações, transportes, manufaturas, dentre outras. Na literatura, há muitos algoritmos que abordam esse tema, sendo os principais o de Dijkstra e o de Ford-Moore-Bellman. Sendo a computação uma aplicação desse problema, o objetivo deste trabalho é mostrar o desempenho do algoritmo de Dijkstra no processo de descobrimento do menor caminho entre roteadores ligados em rede. Para isso, é usado um protocolo amplamente difundido nas redes de computadores chamado Open Shortest Path First
(OSPF). Para demonstrar seu funcionamento, são empregados dois softwares de apoio, o
Dynamips e o Dynagen.
Palavras-chave: Grafos, algoritmo de Dijkstra, redes de computadores, roteadores.
ABSTRACT
The shortest path problem is one of the most studied problems of the graphs theory, because it appears in a lot of applications, such as: computation, telecommunications, transportations, manufacture, etc. In the literature there are many algorithms that approach this subject, where the main algorithms are Dijkstra and Ford-Moore-Bellman. The computation is an application of this problem then, the purpose of this paper is to show the performance of the Dijkstra's algorithm in the process to find the shortest path among linked routers in the network. Then, in this paper is used a known protocol in computer networks called Open Shortest Path First. To demonstrate its operation two softwares, Dynamips and Dynagen, are used.
Key Words: Graphs, Dijkstra’s algorithm, computer networks, routers.
1. INTRODUÇÃO
Com

o

crescimento

da

informática,

sentiu-se

a

necessidade

de

interconectar

computadores, impressoras e outros recursos de informática. Com isso, foi dado