A-otimizacao-de-problemas-de-caminho-mais-curto-entre-dois-pontos-em-uma-rota-utilizando-algoritmos-baseados-em-grafos

Prévia do material em texto

0 
 
FACULDADE NORTE CAPIXABA DE SÂO MATEUS 
ANÁLISE E DESENVOLVIMENTO DE SISTEMAS 
 
 
 
 
ELTON DOUGLAS SILVA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A OTIMIZAÇÃO DE PROBLEMAS DE CAMINHO MAIS CURTO ENTRE DOIS 
PONTOS EM UMA ROTA, UTILIZANDO ALGORITMOS BASEADOS EM 
GRAFOS. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SÃO MATEUS 
2012 
 
 
1 
 
ELTON DOUGLAS SILVA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A OTIMIZAÇÃO DE PROBLEMAS DE CAMINHO MAIS CURTO ENTRE DOIS 
PONTOS EM UMA ROTA, UTILIZANDO ALGORITMOS BASEADOS EM 
GRAFOS. 
 
 
 
Trabalho de Conclusão de Curso apresentado ao 
programa de Graduação no Curso Superior 
Tecnológico em Analise e Desenvolvimento de 
Sistemas da Faculdade Norte Capixaba de São 
Mateus, como requisito para obtenção do grau de 
Tecnólogo em Analise e Desenvolvimento de 
Sistemas. 
Orientador: Lucas Costa Jardim. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SÃO MATEUS 
2012 
 
 
2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Catalogação na fonte elaborada pela “Biblioteca Dom Aldo Gerna”/UNISAM 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
S586o 
 Silva, Elton Douglas 
 A otimização de problemas de caminho mais curto entre dois pontos em uma rota, 
utilizando algoritmos baseados em grafos/– São Mateus: UNISAM /Faculdade Norte 
Capixaba de São Mateus, 2012. 
 
58.f : enc. 
 Orientador: Lucas Costa Jardim 
 Trabalho de conclusão de curso (Tecnólogo em Análise e Desenvolvimento de 
Sistemas) 
UNISAM / Faculdade Norte Capixaba de São Mateus, 2012. 
1.Análise 2. Protótipo 3. Dijkstra I. Silva, Elton Douglas II.UNISAM / 
Faculdade Norte Capixaba de São Mateus, 2012. III. Título. 
 CDD 005.1 
 
 
 
3 
 
ELTON DOUGLAS SILVA 
 
 
 
 
 
A OTIMIZAÇÃO DE PROBLEMAS DE CAMINHO MAIS CURTO ENTRE DOIS 
PONTOS EM UMA ROTA, UTILIZANDO ALGORITMOS BASEADOS EM 
GRAFOS. 
 
 
 
 
Trabalho de Conclusão de Curso apresentado ao programa de Graduação no Curso Superior 
Tecnológico em Analise e Desenvolvimento de Sistemas da Faculdade Norte Capixaba de São 
Mateus, como requisito para obtenção do grau de Tecnólogo em Analise e Desenvolvimento de 
Sistemas. 
 
 
Aprovada em 24 de novembro de 2012 
 
 
 
 
 
COMISSÃO EXAMINADORA 
 
 
 
 
 
_____________________________________________________ 
Profº Lucas Costa Jardim 
Faculdade Norte Capixaba de São Mateus 
Orientador 
 
 
 
 
 
_____________________________________________________ 
Profº Ramilton Costa Júnior 
Faculdade Norte Capixaba de São Mateus 
Membro 1 
 
 
 
 
 
_____________________________________________________ 
Profº Temístocles A. Rocha 
Faculdade Norte Capixaba de São Mateus 
Membro 2 
 
 
4 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Dedico este trabalho a Deus, meu 
Senhor, por ter me dado forças para 
completar este desafio, esta etapa da 
minha vida acadêmica, por me amparar 
nos momentos de angustia e fraqueza, 
pois sei que sem Ele eu não teria 
conseguido. Que toda honra e glória seja 
dada a Ti Senhor. 
 
Dedico aos meus familiares por sempre 
me apoiarem e estarem presentes 
incentivando. 
 
 
5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Meus sinceros agradecimentos ao 
Professor (orientador) Lucas Costa 
Jardim, por ter aceitado este desafio 
comigo, por ter me ajudado nesta batalha 
e por ter contribuindo para a conclusão 
deste projeto. Professor Lucas, muito 
obrigado. 
 
Meus sinceros agradecimentos a Ivani 
Francisca dos Santos, por sua imensa 
ajuda, tanto intelectual quanto pessoal. 
Por sempre está disposta a ajudar sem 
cobrar nada em troca, pelos sinceros 
gestos de tolerância, compreensão e 
carinho. Ivani, muito obrigado. 
 
Meus sinceros agradecimentos a todos os 
professores que fizeram parte da minha 
jornada acadêmica na instituição, sem 
vocês esta jornada não poderia ter sido 
completada. Professores, muito obrigado. 
 
 
6 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
“A arte de programar consiste em 
organizar e dominar a complexidade”. 
(Edsger Dijkstra) 
 
 
7 
 
RESUMO 
 
O presente trabalho tem como objetivo apresentar alguns aspectos sobre a Teoria 
Geral dos Grafos, pseudocódigos que trabalham com grafos buscando a otimização 
(melhor resposta) para encontrar o menor caminho entre dois pontos em uma rota. 
Para o levantamento das informações contidas nesta pesquisa, utilizou-se o 
emprego de uma pesquisa exploratória, respaldando-se em pesquisas bibliográficas 
e virtuais. Para uma melhor visualização, foi desenvolvido um Protótipo, no qual foi 
aplicado o algoritmo selecionado como o mais indicado para solucionar o problema 
proposto nesta pesquisa. A escolha do algoritmo se deu através de comparações 
dos seus valores de complexidade, análise assintótica. 
 
PALAVRAS-CHAVE: Análise. Protótipo. Dijkstra. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
8 
 
ABSTRACT 
 
This work aims to present some aspects about the General Theory of Graphs, 
pseudocódigos working with graphs seeking optimization (best response) to find the 
shortest path between two points on a route. To survey the information contained in 
this research, we used the employment of an exploratory research, supporting 
research into bibliographic and virtual. For best viewing, we developed a prototype, in 
which we applied the algorithm selected as the most suitable for solving the problem 
proposed in this research. The choice of algorithm is made by comparing the values 
of complexity, asymptotic analysis. 
 
KEYWORDS: Analysis. Prototype. Dijkstra. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9 
 
LISTA DE FIGURAS 
 
FIGURA 1.0 – PROBLEMA DADO A EULER EM 1736............................................21 
FIGURA 2.0 - GRAFO MONTADO DO PROBLEMA DADO A EULER EM 1736....22 
FIGURA 3.0 – GRAFO..............................................................................................22 
FIGURA 4.0 – GRAFO DIRECIONADO....................................................................24 
FIGURA 5.0 – GRAFO NÃO DIRECEIONADO..........................................................24 
FIGURA 6.0 – GRAFO PONDERADO......................................................................25 
FIGURA 7.0 – GRAFO SIMPLES.............................................................................25 
FIGURA 8.0 – GRAFO COMPLETO........................................................................25 
FIGURA 9.0 – ALGORTIMOS EM DIAGRAMA DE BLOCOS ................................26 
FIGURA 10.0 - ALGORITMO TEXTUAL..................................................................26 
FIGURA 11.0 – PSEUDOCÓDIGO DO ALGORITMO DE WARSHALL...................27 
FIGURA 12.0 – PSEUDOCÓDIGO DO ALGORITMO DE DIJKSTRA – 
RELAXAMENTO DAS ARESTAS.............................................................................30 
FIGURA 13.0 – GRAFO ORIENTADO.....................................................................31 
FIGURA 14.0 – PSEUDOCÓDIGO ALGORITMO DE BELLMAN-FORD.................32 
FIGURA 15.0 – ANÁLISE ASSINTÓTICA – ............................................................38FIGURA 16.0 – DIAGRAMA DE CASO DE USO – PROTÓTIPO............................44 
FIGURA 17.0 – DIAGRAMA DE ATIVIDADES – EXECUTAR DIJKSTRA...............46 
FIGURA 18.0 – DIAGRAMA DE SEQUÊNCIA.........................................................47 
FIGURA 19.0 – DIAGRAMA DE CLASSE................................................................48 
FIGURA 20.0 – GRAFO PRÉ-DISPOSTO DO PROTÓTIPO..................................49 
FIGURA 21.0 – PROTÓTIPO – TELA PRINCIPAL..................................................50 
FIGURA 21.1 – PROTÓTIPO – TELA PRINCIPAL – PARTE INFERIOR ..............50 
FIGURA 21.2 – PROTÓTIPO – SIMULAÇÃO ENTRADA DE DADOS 
MANUALMENTE......................................................................................................51 
 
 
 
 
 
 
 
 
 
 
10 
 
LISTA DE TABELAS 
 
TABELA 1.0 – SEQUÊNCIA DE DIAGRAMAS – ALGORITMO DE DIJKSTRA........28 
TABELA 2.0 – TABELA COM OS DADOS DO GRAFO DA FIGURA 13.0 ..............31 
TABELA 3.0 –EXEMPLO PL.....................................................................................39 
TABELA 4.0 – COMPLEXIDADE DOS ALGORITMOS.............................................41 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
11 
 
SUMÁRIO 
 
1 INTRODUÇÃO .................................................................................................. 13 
1.1 JUSTIFICATIVA DO TEMA .................................................................................. 13 
1.2 DELIMITAÇÃO DO TEMA ................................................................................... 14 
1.4 OBJETIVOS ........................................................................................................ 15 
1.4.1 OBJETIVO GERAL ................................................................................................ 15 
1.4.2 OBJETIVOS ESPECÍFICOS ..................................................................................... 15 
1.5 HIPÓTESE .......................................................................................................... 15 
1.6 META................................................................................................................... 15 
1.7 METODOLOGIA .................................................................................................. 16 
1.7.1 CLASSIFICAÇÃO DA PESQUISA ............................................................................. 16 
1.7.2 TÉCNICAS PARA COLETA DE DADOS ...................................................................... 17 
1.7.3 FONTES PARA COLETA DE DADOS ......................................................................... 17 
1.7.4 CARACTERIZAÇÃO DA AMOSTRA PESQUISADA ....................................................... 18 
1.7.5 INSTRUMENTO PARA A COLETA DE DADOS ............................................................. 18 
1.7.6 POSSIBILIDADE DE TRATAMENTO E ANÁLISE DOS DADOS. ....................................... 18 
1.8 APRESENTAÇÃO DOS CONTEÚDOS DAS PARTES DO TRABALHO............ 19 
 
2.0 REFERENCIAL TEÓRICO ......................................................................... 20 
2.1 MODELAGEM DE PROBLEMAS .................................................................... 2020 
2.2 TEORIA GERAL DOS GRAFOS .......................................................................... 21 
2.2.1 TIPOS DE GRAFOS ............................................................................................... 23 
2.3 ALGORITMOS ..................................................................................................... 26 
2.3.1 ALGORITMOS DE MENOR CAMINHO OU CAMINHO MÍNIMO ......................................... 27 
2.3.3 ALGORITMO DE BELLMAN-FORD ........................................................................... 31 
2.4 ANÁLISE DE ALGORITMOS ............................................................................... 34 
2.4.1 COMPLEXIDADE DOS ALGORITMOS - ANÁLISE ASSINTÓTICA .................................... 35 
2.4.2 PROGRAMAÇÃO LINEAR.......................................................................................39 
2.4.3 ALGORITMO ESCOLHIDO ...................................................................................... 41 
2.5 FERRAMENTAS (IDE’S) E LINGUAGEM UTILIZADAS NO DESENVOLVIMENTO 
DO SOFTWARE ........................................................................................................ 42 
 
 
12 
 
2.5.1 C# ..................................................................................................................... 42 
2.5.2 UML - UNIFIED MODELING LANGUAGE OU LINGUAGEM DE MODELAGEM DE DADOS .... 42 
 
3.0 IMPLEMENTAÇÃO DIJKSTRA – PROTÓTIPO ................................... 44 
3.1 DIAGRAMA DE CASO DE USO .......................................................................... 44 
3.1.2 DIAGRAMA DE ATIVIDADES ................................................................................... 45 
3.1.3 DIAGRAMA DE SEQUÊNCIA ................................................................................. 466 
3.1.4 DIAGRAMA DE CLASSES..................................................................................... 477 
3.2 GRAFO DE ESTUDOS – PROTÓTIPO ............................................................. 488 
3.3 PROTÓTIPO ..................................................................................................... 499 
3.3.1 IMPLEMENTAÇÃO DO ALGORITMO DE DIJKSTRA EM C SHARP ............................... 522 
 
4.0 CONCLUSÃO E RECOMENDAÇÕES .................................................. 555 
4.1 CONCLUSÃO .................................................................................................... 555 
4.2 RECOMENDAÇÕES ......................................................................................... 555 
 
5.0 REFERÊNCIAS BIBLIOGRÁFICAS ...................................................... 577 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13 
 
1 INTRODUÇÃO 
 
Gastos e tentativa de otimização, são fatores comuns no cotidiano de pessoas 
físicas e jurídicas. Quem nunca se perdeu ou gastou mais combustível errando o 
caminho para a casa de um “primo” que morava em outra cidade? Qual empresa 
que nunca mudou uma rota dos seus veículos tentando achar o caminho mais curto 
ou mais econômico para atingir ou concluir determinada meta? Bem, hoje com as 
novas tecnologias (como o GPS) estes tipos de problemas se tornaram mais fáceis 
de contornar. 
 
Este trabalho abordará algoritmos que trabalham na otimização desses problemas 
(menor caminho, melhor rota), os quais (os problemas) podem ser montados 
graficamente utilizando grafos. 
Padrões algorítmicos que foram criados para fins parecidos também foram 
abordados, assim como a teoria dos grafos (onde foram apresentados apenas os 
conceitos básicos, acreditando-se dar um bom suporte para o acompanhamento da 
pesquisa). 
 
Na etapa final foi desenvolvido um software (protótipo) no qual está implementado o 
algoritmo que se foi identificado como o mais indicado para otimização deste tipo de 
problema (menor caminho entre dois pontos de uma rota), onde o mesmo pode ser 
alimentado diretamente pelo usuário. 
 
 
1.1 JUSTIFICATIVA DO TEMA 
 
Solução e otimização de problemas, são resultados constantemente buscados pela 
humanidade. Trabalhos, pesquisas e abundantes denotações científicas foram e são 
criadas para tais feitos. Uma das formas encontradas e utilizadas para obtenção da 
otimização e solução de famosos problemas dados à sociedade (pontes de 
Königsberg em 1736, o problema das 4-Cores de FrancisGuthris/De Morgan em 
1852), foi o uso da Teoria dos Grafos. 
 
14 
 
A Teoria dos Grafos é vista como uma das mais importantes áreas da matemática 
discreta, a mesma é utilizada na construção de modelos para a visualização dos 
problemas de um ângulo proporcionalmente melhor. 
Com o avanço tecnológico depois da criação do primeiro computador eletrônico 
(Eniac – 1946), o desenvolvimento e estudo dos algoritmos foram impulsionados. 
 
Segundo Oliveira e Nunes (2011), nos anos 70 e 80 ocorrendo o desenvolvimento 
da base matemática da Teoria dos Grafos, a mesma passou a ser utilizada com a 
informática, na época na área de Análise de Redes Sociais. 
 
Como fora demonstrado, a Teoria dos Grafos, ajudou e poderá ajudar a modelar 
problemas de diversos setores de “N” áreas, que poderão abranger desde 
problemas pequenos como serviços de entrega de pizzas ou problemas maiores 
como atendimento bancário de aposentados, menor caminho entre dois pontos de 
uma rota, dentre outros. Uma vez modelado o problema em questão, se pode utilizar 
de algoritmos para ajudar na otimização do mesmo. 
 
 
1.2 DELIMITAÇÃO DO TEMA 
 
O presente trabalho, através de pesquisas (bibliográficas e virtuais), visa obter 
informações e abordar métodos (algoritmos) que foram desenvolvidos com o 
objetivo de trazer respostas mais computacionais (rápidas e mais precisas) para 
otimização de problemas de caminho mais curto entre dois pontos de uma rota. 
 
 
1.3 FORMULAÇÃO DO PROBLEMA 
 
Baseando-se na diminuição de gastos e tempo, ao se otimizar qualquer processo de 
um determinado trabalho, estamos gerando lucro e ou diminuição de custos. 
Qual o algoritmo que melhor se enquadra para se obter de forma otimizada, o menor 
caminho entre dois pontos de uma rota? 
 
 
15 
 
1.4 OBJETIVOS 
 
 
1.4.1 OBJETIVO GERAL 
 
Apresentar a utilização de algoritmos baseados em grafos na otimização de 
problemas de menor caminho em uma rota, através um software (protótipo) que foi 
desenvolvido, podendo o mesmo ser alimentado diretamente pelo usuário. 
 
 
1.4.2 OBJETIVOS ESPECÍFICOS 
 
 Pesquisar sobre algoritmos que tratam de problemas de menor 
caminho. 
 Levantar informações sobre a Teoria dos Grafos. 
 Identificar qual o melhor algoritmo para se trabalhar com problemas de 
menor caminho, onde o mesmo só utilize pesos de valores positivos. 
 Desenvolver um software (protótipo) onde será aplicado um algoritmo 
que melhor se enquadre no problema posposto nesta pesquisa e que 
tenha a menor taxa de complexidade (valor assintótico), o qual irá 
identificar o menor caminho entre dois pontos em uma rota. 
 
 
1.5 HIPÓTESE 
 
Acredita-se que ao final desta pesquisa, será possível enxergar a praticidade e 
agilidade que se ganha ao implementarmos algoritmos baseados em grafos em 
softwares que indicam o menor caminho entre dois pontos de uma rota. 
 
 
1.6 META 
 
Expor como a aplicabilidade de algoritmos baseados em grafos pode ajudar na 
otimização de problemas de menor caminho em uma rota. 
16 
 
1.7 METODOLOGIA 
 
Para Viegas (apud Reis, 2008, p. 44), “a metodologia é o conjunto de técnicas e 
processos utilizado pela ciência para formular e resolver problemas de aquisição 
objetiva do conhecimento de maneira sistemática.”. 
 
Na metodologia, utiliza-se de técnicas propostas para obtenção de êxito do 
problema proposto na pesquisa elaborada. Trabalhando com a mineração dos dados 
pesquisados e fornecidos, mostrando as formas com que os mesmos foram 
modelados. 
 
 
1.7.1 CLASSIFICAÇÃO DA PESQUISA 
 
Para Gil (2007), é possível classificar as pesquisas em três grandes grupos: 
exploratórios, descritivas e explicativas. Onde as pesquisas exploratórias envolvem 
levantamento bibliográfico, entrevistas com pessoas que tiveram experiências 
práticas com o problema pesquisado e ou análise de exemplos. Já as pesquisas 
descritivas têm o objetivo primordial à descrição das características dos fatores 
estudados e estabelecendo as relações entre variáveis. Nas pesquisas explicativas 
a preocupação central seria identificar os fatores que determinam ou que contribuem 
para a ocorrência dos fenômenos, portanto, é neste tipo de pesquisa onde há um 
maior aprofundamento da realidade, pois a mesma explica o porquê das coisas. 
 
Reis (2008, p.51), dentro das pesquisas exploratórias, descreve bem o conceito da 
pesquisa bibliográfica: 
 
A pesquisa bibliográfica é a mais simples técnica de pesquisa. Ela explica 
um problema, fundamentando-se apenas nas contribuições secundárias, ou 
seja, nas informações e dados extraídos de livros de leitura corrente e de 
referencias, de revistas impressas e virtuais, material audiovisual, 
entrevistas, documentos, etc. de diferentes autores que versam sobre o 
tema selecionado para o estudo. 
 
Foi utilizada para a conclusão do projeto a pesquisa exploratória, respaldando-se 
nos levantamentos de dados e análise de exemplos que serão obtidos através de 
17 
 
pesquisas bibliográficas e virtuais, visto que, não foram abordados problemas de 
empresas ou setores reais, mas sim, exemplos para a compreensão do trabalho 
proposto. 
 
 
1.7.2 TÉCNICAS PARA COLETA DE DADOS 
 
Richardson (1999, p. 219) “as técnicas de pesquisa não podem ser utilizadas como 
receitas de instrumentos neutros, mas como meios de obtenção de informação cujas 
qualidades e limitações devem ser controladas”. 
 
Qualquer técnica utilizada para coleta de dados em um referido problema, pesquisa 
e ou trabalho, não pode se utilizar de meios estagnados, parados, é preciso 
observar o que se procura encontrar e quais os meios que estão sendo utilizados 
para determinado fim. 
Foram utilizadas no referente trabalho, técnicas de coleta e levantamento de dados 
em fontes bibliográficas e virtuais (sites, fóruns, artigos). 
 
 
1.7.3 FONTES PARA COLETA DE DADOS 
 
As fontes para coletas de dados podem ser dividir em dois tipos: os de fontes 
primárias e fontes secundárias. 
Segundo Andrade (2001), fontes primárias são formadas por obras ou textos 
originais, conteúdos ainda não trabalhados, sobre determinado assunto. As fontes 
primárias, pela sua relevância, dão origem a outras obras, que vão formar uma 
literatura ampla sobre aquele determinado assunto. 
 
Para Cervo e Bervian (apud MERTENS; FUMANGA; TOFFANO; SIQUEIRA, 2007, 
p. 60) “as fontes secundárias são provenientes de material bibliográfico colhido em 
livros, revistas periódicas, jornais, anais de congressos e demais fontes impressas 
ou eletrônicas”. 
18 
 
Seguindo estas linhas de raciocínio, foram utilizadas fontes secundárias, pois o 
mesmo trabalhou com pesquisas bibliográficas e virtuais, atribuindo a base do seu 
conteúdo nas informações adquiridas com as pesquisas. 
 
 
1.7.4 CARACTERIZAÇÃO DA AMOSTRA PESQUISADA 
 
O trabalho foi realizado através de pesquisas bibliográficas (livros, fontes impressas, 
etc.) e virtuais (sites, artigos, fóruns), esperando adquirir informações necessárias 
para a conclusão do mesmo com êxito. 
 
 
1.7.5 INSTRUMENTO PARA A COLETA DE DADOS 
 
Utilizaram-se pesquisas bibliográficas e virtuais, assim como leituras de materiais 
impressos que se correlacionavam com o tema e problema sugeridos nesta 
pesquisa. 
Não se fez necessário a utilização de questionário ou outros instrumentos 
semelhantes para coleta de dados referentes à pesquisa proposta. 
 
 
1.7.6 POSSIBILIDADE DE TRATAMENTO E ANÁLISE DOS DADOS 
 
Para Vergara (2003, p. 59), ”Tratamento dos dados refere-se àquela seção na qual 
se explicita para o leitor como se pretendetratar os dados a coletar [...].”. 
 
Partindo dessa premissa e visando elaborar uma pesquisa integra e sem erros, todo 
o conteúdo pesquisado foi analisado, buscando evitar dados não precisos e 
redundância de informações. 
 
 
 
 
 
19 
 
1.8 APRESENTAÇÃO DOS CONTEÚDOS DAS PARTES DO TRABALHO 
 
Para a demonstração do objeto de estudo desta pesquisa, a mesma foi dividida em 
05 capítulos: 
Onde no primeiro capítulo é feita a Introdução, Justificativa do Tema, Delimitação do 
tema, Formulação do problema, Objetivos (geral e específicos) e a Hipótese. 
 
No segundo capítulo é exposto o Referencial Teórico, o qual fundamentaliza esta 
pesquisa. 
 
O terceiro capítulo apresenta o Protótipo, o qual se torna a parte prática deste 
projeto, onde foi inserido o algoritmo (dentre os abordados por esta pesquisa) que 
melhor se enquadrou para a resolução do problema proposto. 
 
As Conclusões referentes a esta pesquisa e Recomendações para continuação do 
protótipo (possíveis melhorias), setores onde o mesmo poderia ser empregado, etc., 
encontram-se no capítulo 4. 
 
No capítulo 5 estão todas as referências bibliográficas utilizadas para a conclusão 
deste projeto. 
 
20 
 
2.0 REFERENCIAL TEÓRICO 
 
 
2.1 MODELAGEM DE PROBLEMAS 
 
Ao tentarmos obter uma visualização mais ampla e com representações mais 
simplificadas de um determinado problema, a modelagem pode ser uma excelente 
ferramenta a se utilizar. 
Para Goldbarg e Luna (2005, p. 2) “Os modelos são representações simplificadas da 
realidade que preservam, para determinadas situações e enfoques, uma 
equivalência adequada.”. 
Expondo-se um problema que antes se encontrara em forma contextual, para um 
modelo visual (gráfico), fará com que se obtenha uma melhor amplitude do mesmo, 
consequentemente, se atribuirá uma otimista capacidade para a simplificação do 
mesmo. 
É importante lembrar que, todo modelo deve passar por um processo de validação, 
onde ocorrem verificações da sua representatividade, é verificado se o modelo 
realmente está de acordo com a atividade para o qual foi elaborado. 
O conceito que é aferido aos modelos, de que eles demonstram uma representação 
substituta da realidade, implicam em um alcance limitado. 
 
Goldbarg e Luna (2005) relata que para alcançarmos modelos eficientes, são 
necessárias pelo menos três habilidades: Foco holístico, que seria indispensável 
quando estamos procurando solucionar um problema e nossa solução pode criar 
outros problemas que podem posteriormente anular nossos esforços; Tratamento 
eclético da dimensão da análise, onde todos os métodos utilizados terão de ser os 
mais livremente dispostos, e por último a Tradução adequada, onde se indica que, 
para se ter um bom modelo, se exigirá ter uma boa tradução de todos os dados e 
contexto do problema. 
 
 
 
 
21 
 
2.2 TEORIA GERAL DOS GRAFOS 
 
A Teoria dos Grafos é vista como uma das mais importantes áreas da matemática 
discreta e também na área da Ciência da Computação. 
Alguns autores como Bonchev e Rouvray (1991), relatam que o primeiro registro 
conhecido da teoria dos grafos foi feito pelo matemático suíço Leonhard Euler, que 
viveu entre 1707 e 1783, o qual utilizou a mesma pela primeira vez em 1736 para 
resolver um problema que lhe foi entregue pelos cidadãos da cidade prussiana de 
Königsberg, a qual era cortada pelo rio Pregel, que abrange uma porção de terra 
(ilha). O problema que lhe foi proposto era determinar se era passível começar um 
passeio por qualquer ponto das margens do rio (Pregel), ou da ilha, e percorrer por 
todas as pontes (eram 07 no total), cada uma somente uma única vez, e voltar ao 
ponto de partida. 
 
Figura 1.0 – Problema dado a Euler em 1736 
Fonte: DEWDNEY. 20.000 léguas matemáticas, (2000). 
 
Montando o problema em um grafo, em 1736, Euler mostrou que este passeio é 
impossível, que o mesmo só seria possível, se em cada ponto (ilha) houvesse duas 
pontes, uma para entrada e outra para saída, formando assim em cada ponto um 
número par de pontes. 
 
A figura 2.0 ilustra um possível esboço feito por Euler, montado o problema proposto 
a ele em forma de grafo. 
 
 
 
22 
 
 
 
Figura 2.0 – Grafo montado do problema dado a Euler em 1736 
Fonte: DEWDNEY, 20.000 léguas matemáticas, (2000). 
 
Goodrich e Tamassia (2007) relatam de forma simples, porém direta, o conceito de 
grafos, onde dizem que um grafo é uma forma gráfica de representar 
relacionamentos que existem entre pares de objetos. 
Um grafo de forma simples, nada mais é que a representação visual (gráfica) de 
elementos que se interligam e que de certa forma tem uma interdependência entre 
si. O mesmo pode ser amplamente utilizado para representação visual de 
problemas, onde trará uma melhor visualização do mesmo. 
Os elementos do grafo são denominados de vértices (nós), que é um conjunto não 
vazio de objetos e estão interligados através de traços, denominados arestas, que 
são um conjunto de pares não ordenados. 
Para um melhor entendimento, podemos imaginar uma árvore (no conceito de 
árvores binárias em algoritmo), vários elementos (vértices) que estão ligados entre si 
graficamente através de traços (arestas). 
A figura 3.0 ilustra um exemplo simples de grafo. 
 
 
 
 
 
 
 
 
 Figura 3.0 – Grafo 
 Fonte: Fonte: Adaptado pelo autor 
23 
 
No seu conceito matemático, um grafo é G(V, A), onde V são os vértices e A as 
arestas, o conjunto V = {1, 2,..., v} será composto dos “n” nós do grafo, e A = {1, 2,..., 
a} conterá as “n” arestas. Sendo que, dependendo da situação, as arestas podem 
ser direcionadas ou não, e também podem trazer sobre si pesos (valores numéricos) 
associados, tornando-os assim Grafos Ponderados. 
Partindo do seu conceito matemático, temos então na figura 3.0, os seguintes dados 
representando G(V, A): 
V = {2,4,5,6,8}; 
A = { { 2, 4} { 2, 6} { 4, 2} { 4, 5} { 4, 6} { 5, 4} { 5, 6} { 6, 2} { 6, 4} { 6 ,5} {8, 4}}; 
 
Outro ponto importante na teoria dos grafos é entender como os vértices podem 
estabelecer vínculos (ligações) através das arestas, definindo-se assim a vizinhança 
de vértices. 
Caso não haja valores associados às arestas, dizemos que o grafo é Rotulado. Não 
se encontrando também orientação nas arestas, ou seja, direcionamento da direção 
da mesma, e sendo um vértice ‘A’ “amigo” do vértice ‘B’ e vice-versa, os mesmos 
possuem uma relação simétrica. 
 
Goldbarg e Luna (2005, p. 489) dizem que “[...] dois vértices xi e xj são vizinhos ou 
adjacentes quando existe uma aresta que liga xi a xj ou vice-versa.”. 
É válido ressaltar que a noção de vizinhança se dá apenas a grafos não orientados. 
 
 
2.2.1 TIPOS DE GRAFOS 
 
Dentre os diversos tipos de grafos, existem os direcionados e não direcionados. 
Para Goldbarg e Luna (2005, p. 485), “um grafo é dito direcionado quando o sentido 
das ligações entre os vértices é importante. Nesse caso normalmente as arestas são 
chamadas por arcos.”. 
 
Para obtenção de uma boa noção do que são grafos direcionados ou dígrafos, basta 
pensarmos no grafo de um bairro, onde temos como os vértices (nós) alguns pontos 
do bairro e as arestas seriam as ruas, que interligam os pontos do bairro entre si. O 
contexto de direcionado está no fator de mão e contramão, imaginemos que para 
24 
 
irmos da prefeitura da cidade que está localizada neste bairro, até o fórum, podemos 
ir pela rua principal, mas para voltarmos à prefeitura, a mesma rua não é permitida, 
pois é via de mão única, assim como uma aresta de um grafo direcionado, ela tem 
sentido certodenominado. Vale ressaltar que nos grafos direcionados, as arestas 
são substituídas por setas que indicam o vértice de destino e o sentido (direção) da 
mesma. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Figura 4.0 – Grafo direcionado 
 Fonte: Adaptado pelo autor 
 
Já o conceito de grafo não direcionado, ou apenas grafo, é justamente o oposto do 
direcionado, pois as arestas não implicam em uma direção precisa de segmento, e 
se pode associar a cada aresta um subconjunto de dois ou de um elemento de V 
(conjunto de vértices), indicando as localidades finais. 
 
 
 
 
 
 
 Figura 5.0 – Grafo não direcionado 
 Fonte: Adaptado pelo autor 
 
25 
 
Outro tipo de grafo é o ponderado, para Ziviane (2005, p. 255), “um grafo ponderado 
possui pesos associados às suas arestas”. Neste modelo, os valores que estão 
associados influenciam nas decisões de escolha do caminho, pois os custos sobre 
cada aresta podem variar. Este tipo de grafo é muito utilizado em problemas de 
caminho mínimo, que visa à diminuição (otimização) de custos ao atravessar o grafo 
na rota referida pelo problema. 
 
 10 
 
 
 15 
 22 
 
 35 
 
 Figura 6.0 – Grafo ponderado 
 Fonte: Adaptado pelo autor 
 
Quando se tem um grafo simples e uma ligação associada a cada par de vértices, é 
dito que o mesmo é completo. Este conceito é dado, pois ha uma ligação, 
comunicação, entre todos os vértices, podendo se ir a qualquer parte do grafo 
partindo de qualquer vértice. 
 
As figuras abaixo (figura 7.0 e figura 8.0) distinguem bem um grafo simples de um 
grafo completo. Lembrando que a diferença está em que, em um grafo simples não 
se apresentam laços nem arestas paralelas, e o grafo completo é um grafo simples, 
mas todos os vértices estão interligados. 
 
 
 
 
 
 
 
Figura 7.0 – Grafo simples Figura 8.0 – Grafo completo 
Fonte: Adaptado pelo autor Fonte: Adaptado pelo autor 
A 
D 
C 
B 
26 
 
2.3 ALGORITMOS 
 
Para Said (2007, p. 07), algoritmo é “[...] uma sequência finita de passos, descritos 
em uma ordem lógica, que visam a atingir um objetivo bem definido.”. 
Resumindo, algoritmo é um passo a passo estruturado, finito, elaborado com o 
intuito de se conseguir realizar um objetivo determinado, tarefa, cálculo, receita, etc. 
 
A importância dos algoritmos é indiscutível, pois como o mesmo fora descrito 
anteriormente, ele é uma sequência finita de passos, algo lógico para se atingir 
determinada meta, o mesmo pode partir das primícias de uma bula de remédios até 
áreas computacionais, matemáticas etc. 
 
Um algoritmo pode ser feito (aplicado) geralmente de duas formas: gráfica, onde 
para uma melhor visualização serão utilizados diagramas de blocos; e de forma 
textual, onde será utilizada linguagem de programação. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 9.0 – Algoritmos em diagrama de blocos Figura 10.0 – Algoritmo textual 
Fonte: BAJPAI; MUSTOE; VALKER Fonte: Adaptado pelo autor 
Matemática para engenheiros. (1980). 
 
27 
 
2.3.1 ALGORITMOS DE MENOR CAMINHO OU CAMINHO MÍNIMO 
 
A definição de caminho é clara, está ligada na rota e na distância entre dois pontos, 
um passeio sem vértices repetidos. Sabendo-se disso, é fácil entender que, a 
distância de um vértice z, em um grafo G, até o vértice y, do mesmo grafo, é a soma 
dos pesos das respectivas arestas existentes entre os dois vértices. Logicamente 
admitindo que exista ligação entre os dois vértices. 
Então, é correto dizer que K é o menor caminho entre z e y, caso não acha outros 
caminhos. 
Para verificar a existência de caminho entres dois vértices de um grafo, temos de 
observar suas ligações (arestas). 
 
Muito utilizado para determinado fim, é o algoritmo de Floyd-Warshall (ou Warshall). 
Ele trabalha com a busca do caminho mais curto (entre os pontos de uma rota) de 
um grafo dirigido e com pesos, valores (grafo valorado). 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 11.0 – Pseudocódigo do algoritmo de Warshall 
Fonte: GOODRICH, TAMASSIA. Estrutura de dados e algoritmos em Java. (2007). 
 
O algoritmo de Dijkstra foi criado por um cientista da computação holandês, 
chamado Edsger Wybe Dijkstra (Roterdã, 11 de Maio de 1930 – Nuenen, 6 de 
Agosto de 2002), aproximadamente no final da década de 50. 
 
Goodrich e Tamassia (2007) relatam que, ao se tentar descobrir o caminho mais 
curto de v a qualquer outro ponto do grafo, o algoritmo de Dijkstra é uma das 
28 
 
primeiras opções, pois como ele é considerado um método guloso, a sua aplicação é 
tida como uma grande nuvem, que vai se expandindo e inserindo nela os vértices do 
grafo, até não sobrar vértice algum de fora da nuvem. Tendo assim ao final do 
processo, encontrado o menor caminho de v para qualquer outro vértice (nó) do 
grafo. 
 
Basicamente o algoritmo de Dijkstra funciona buscando e comparando os valores 
(pesos) das arestas adjacentes ao vértice de origem, inicialmente deixando todos os 
outros vértices com o custo “infinito”, ainda não descoberto. Conforme o algoritmo 
vai avançando pelo grafo, o mesmo vai “marcando”, selecionando os vértices com 
menores pesos, colocando neles “tarjas”, sinais, marcadores que podem ser 
temporários ou definitivos, indicando as arestas de menor distancia entre o vértice 
de origem até o vértice atual, sendo considerado um método guloso, pois vai 
selecionando e escolhendo o menor caminho encontrado até o momento, lógico, 
enquanto o algoritmo não chega ao fim. Chegando ao final do grafo, o algoritmo 
assim, consegue identificar, o menor caminho entre os dois pontos (vértices) do 
grafo. Pois terá obtido e marcado as arestas e vértices com menor custo. 
Ressaltando que, o algoritmo de Dijkstra trabalha com grafos dirigidos ou não, e 
ponderados com valores apenas positivos. 
 
A tabela abaixo ilustra o funcionamento do algoritmo de Dijkstra através de uma 
sequencia de diagramas. 
 
Algoritmo de Dijkstra – Sequencia de Diagramas (Continua até pág. 30). 
 Inicialmente todos os nodos tem um custo 
infinito, 
exceto s (a raiz da busca) que tem valor 0: 
vértices s u v x y 
estimativas 0 ∞ ∞ ∞ ∞ 
precedentes - - - - - 
 
 
29 
 
 selecione s (vértice aberto de estimativa 
mínima) 
 feche s 
 recalcule as estimativas de u e x 
vértices s u v x y 
estimativas 0 10 ∞ 5 ∞ 
precedentes s s - s - 
 
 selecione x (vértice aberto de estimativa 
mínima) 
 feche x 
 recalcule as estimativas de u,v e y 
vértices s u v x y 
estimativas 0 8 14 5 7 
precedentes s x x s x 
 
 selecione y (vértice aberto de estimativa 
mínima) 
 feche y 
 recalcule a estimativa de v 
vértices s u v x y 
estimativas 0 8 13 5 7 
precedentes s x y s x 
 
 selecione u (vértice aberto de estimativa 
mínima) 
 feche u 
 recalcule a estimativa de v 
vértices s u v x y 
estimativas 0 8 9 5 7 
precedentes s x u s x 
 
 
 
 
 
30 
 
 selecione v (vértice aberto de estimativa 
mínima) 
 feche v 
vértices s u v x y 
estimativas 0 8 9 5 7 
precedentes s x u s x 
 
 
 
Tabela 1.0 – Sequencia de diagramas – Algoritmo de Dijkstra (Parte final da tabela - pág. 28, 29, 30). 
Fonte: MARIANI – (Livro eletrônico) Site http://www.inf.ufsc.br/grafos/ (2012) 
 
A figura 12.0 traz o pseudocódigo do algoritmo de Dijkstra, baseando no exemplo 
dado domesmo ser como uma nuvem, utilizando um recurso de “relaxamento de 
aresta”, onde o relaxamento é dado por um caminho entre as arestas, ex (k, j), 
tornando o relaxamento como uma espécie de mola, pois o mesmo vai se esticando 
do ponto único de origem até o final, voltando ao ponto de partida, tendo assim o 
resultado do melhor caminho. 
 
Goodrich e Tamassia (2007) dizem que, seu principio básico é dado por: 
 Se D[u] + w((u, z)) < D[z] então 
 D[z] <- D[u] + w((u, z)); 
Onde D[u] é um rótulo, espécie de vetor ou pilha para cada vértice de u em V. 
 
 
 
Figura 12.0 – Pseudocódigo do Algoritmo de Dijkstra – Relaxamento das arestas 
Fonte: GOODRICH e TAMASSIA (2007). 
 
31 
 
2.3.3 ALGORITMO DE BELLMAN-FORD 
 
O algoritmo de Bellman-Ford, criado por Richard Bellman e Lester Ford Jr, também é 
um algoritmo de busca de caminho mínimo, basicamente sua diferença do Dijkstra, é 
que, este aceita pesos negativos em suas arestas, enquanto o Dijkstra só aceita 
valores positivos. 
Levando-se em consideração o tempo gasto no processamento, o Dijkstra leva 
vantagem, mas como dito antes, só trabalha com valores positivos em suas arestas. 
 
Goodrich e Tamassia (2007) ressaltam que, devemos sempre buscar fazer com que 
o grafo em que está sendo aplicado o algoritmo, deva ser um dígrafo (direcionado), 
pois de outra forma (grafo não direcionado) poderíamos ir e vir por uma mesma 
aresta, podendo ocorrer um loop (ciclo), deixando os pesos das arestas negativos, e 
caso isso ocorra, se perderia o valor da distância entre os vértices, pois valores 
negativos invalidam a noção de distância baseada no peso das arestas. 
 
O algoritmo de bellman-ford, é mais fácil de ser compreendido e aplicado do que o 
de Dijkstra. Tendo como exemplo o grafo da figura 13.0, é possível criar uma tabela 
com os vértices de origem, destino e a distancia entre eles, criando uma maneira 
mais didática para o entendimento da forma de aplicação e funcionamento do 
algoritmo. 
 
 
Figura 13.0 – Grafo orientado Tabela 2.0 – Tabela com os dados do grafo 
Fonte: Adaptado pelo autor. da figura 13.0. 
 Fonte: Adaptado pelo autor. 
Origem Destino Distância 
(Peso) 
A B 4 
A C 2 
B A 4 
B D -5 
C A 2 
C E 3 
D C 8 
E D -6 
 
32 
 
O algoritmo de bellman-ford, baseia-se em: 
 
 
Figura 14.0 – Pseudocódigo algoritmo de Bellman-ford 
Fonte: GOODRICH, TAMASSIA. Projeto de Algoritmos: Fundamentos, análise e exemplos da 
Internet. (2004). 
 
Tendo como exemplo os dados da figura 13.0 e da tabela 2.0, a aplicação do 
algoritmo de Bellman-ford (com a linguagem C/C++), se daria da seguinte maneira: 
 
#include <iostream> 
 #define INFINITY 0x3f3f3f3f 
 #define NODOS 1000 
 
using namespace std; 
 
 typedef struct { 
 int source; 
 int dest; //destino 
 int weigth; // peso 
 }Edge; 
 
 int distancia[NODOS]; 
 
 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) { 
33 
 
 int i,j,trocou; 
 for (i = 0; i < nodecount; i++) { 
 distancia[i] = INFINITY; 
 } 
 distancia[source] = 0; 
 for (i = 0; i < nodecount; i++) { 
 trocou = 0; 
 for (j = 0; j < edgecount; j++) { 
 if(distancia[edges[j].dest] > distancia[edges[j].source] + edges[j].weigth) { 
 distancia[edges[j].dest] = distancia[edges[j].source] + edges[j].weigth; 
 trocou = 1; 
 } 
 } 
 
 //se nenhuma iteração teve efeito, futuras iterações estão dispensadas 
 if (trocou == 0) break; 
 
 } 
 
 //usado somente para detectar ciclos negativos (dispensável) 
 for (i = 0; i < edgecount; i++) { 
 if (distancia[edges[i].dest] < distancia[edges[i].source + edges[i].weigth]) { 
 cout << "Ciclo negativo de pesos de arestas detectado" << endl; 
 break; 
 } 
 } 
 
 for (i = 0; i < nodecount; i++) { 
 cout << "A distancia mais curta entre os nodos " << source << " e " << i <<" 
eh " << distancia[i] << endl; 
 } 
 } 
 int main(int argc, char *argv[]) 
 { 
34 
 
 //Este caso de teste produzira as distancias entre o nodo 0 e os outros nodos 
 Edge Arestas[8] = {{0, 1, 4}, {0, 2, 2}, {1, 0, 4}, {1, 3, -5}, 
 {2, 0, 2}, {2, 4, 3}, {3, 2, 8}, {4, 3, -6}}; 
 
 
 // BellmanFord(Estrutura,arestas,vertices,origem); 
 BellmanFord(Arestas,8,5,0); 
 system("PAUSE"); 
 return 0; 
 } 
 
 
2.4 ANÁLISE DE ALGORITMOS 
 
Análise de Algoritmos é uma importante área da Ciência da Computação onde são 
estudados os recursos e ou tempo necessários para a execução de um determinado 
algoritmo. 
 
Ziviane(2005, p. 03) relata que: 
 
Depois que um problema é analisado e decisões de projeto são finalizadas, 
o algoritmo tem de ser implementado em um computador. Neste momento, 
o projetista tem de estudar as várias opções de algoritmos a serem 
utilizados, em que os aspectos de tempo de execução e espaço ocupado 
são considerações importantes. 
 
Quando o tema em análise de algoritmos é Medida do Tempo de Execução de um 
Programa, é preciso se preocupar ou ficar atento em pelo menos dois tipos distintos 
de problemas quando, for feita a análise de um algoritmo em particular e a análise 
de uma classe de algoritmos. 
 
Knuth (apud Ziviane, 2005, p. 03) aborda que na análise de um algoritmo em 
particular, é necessário saber qual é o custo de usar um dado algoritmo para 
resolver um problema específico, que neste caso deverão ser investigadas as 
características importantes do algoritmo em questão (número de vezes que cada 
parte do algoritmo deve ser executada). Já na análise de uma classe de algoritmos, 
35 
 
devemos nos atentar para a seguinte pergunta: qual é o algoritmo de menor custo 
possível para resolver um problema particular? Geralmente neste tipo de análise, 
toda uma estrutura (família) de algoritmos destinados ao mesmo tipo de problema 
deve ser analisada. 
 
Algumas técnicas e ou maneiras são utilizadas para medirmos o custo de utilização 
de um algoritmo. A implementação do mesmo (algoritmo em questão) em um 
computador real, seria uma das maneiras para a medição do custo de utilização 
(método empírico). Mas será que os dados obtidos por este tipo de medição, seriam 
precisos? 
Partindo do pressuposto que o algoritmo deveria ser ótimo (trabalhar conforme o 
esperado ou seu custo ser menor ou igual ao custo possível) sem interferências de 
fatores não correlatos, é correto afirmar que, não poderemos ter uma medição 
precisa, já que vários fatores poderiam influenciar, tais como: quantidade de 
memória, processador, compilador utilizado, etc. 
 
Para encontrarmos meios mais contundentes e adequados, precisamos utilizar 
métodos matemáticos, definindo o número de operações a serem executadas e o 
custo de cada operação (complexidade dos algoritmos). No final se compararmos 
algoritmos destinados à resolução de um mesmo tipo de problema, com algum custo 
estimado e ou esperado, podemos então ter uma base de qual algoritmo teve um 
desempenho melhor. Ou ainda podemos considerar ou analisar, como foi 
mencionado anteriormente, somente as partes mais relevantes do código, como os 
loops, abstraindo assim as outras partes (como atribuição). 
 
 
2.4.1COMPLEXIDADE DOS ALGORITMOS - ANÁLISE ASSINTÓTICA 
 
Segundo Merdina e Fertig (2006) os algoritmos podem ter sua classificação definida 
pelo tipo de expressão matemática que defini seu comportamento na análise de 
complexidade. Para isso se utiliza o comportamento assintótico da função do tempo 
“T” em relação ao tamanho da entrada do algoritmo (n). 
 
36 
 
O tempo de resposta de um algoritmo está intrinsicamente ligado ao tamanho da 
entrada dos dados (n) e também a forma como os dados são inseridos (melhor caso, 
pior caso e resultado esperado ou estimado). 
 
A análise assintótica ignora constantes dependentes da máquina e olha em vez do 
tempo real de execução, o crescimento do tempo de execução T(n). 
Basicamente, é correto afirmar que, a análise assintótica não define expressamente 
o número total de passos e ou operações que um algoritmo fará, mas ilustra o 
comportamento que o mesmo terá quando variamos o valor da entrada dos dados 
(n). 
 
A classe assintótica é representada também pela notação O. 
Merdina e Fertig (2006) apontam algumas classes com esta notação: 
 
 Constante: O(1) 
 Logarítmica: O(lg(n)) (representamos logaritmo na base 2 como lg) 
 Linear: O(n) (lê-se “O de n” ou “Ordem de n”) 
 Quadrática: O(n²) 
 Cúbica: O(n³) 
 Exponencial: O(cn), onde c é uma constante. 
 
Tendo como base as informações dadas neste tópico, vamos tentar analisar um 
simples algoritmo que trabalhe em função da resposta de uma simples somatória: 
 
O pseudocódigo para este algoritmo ficaria assim: 
 
Inicio 
somatoria numérico; 
somatoria  0; 
para i  2 até n faça 
 somatoria  somatoria + i*i*i*i*i*i; 
fimpara 
37 
 
escreva(somatoria); 
fim 
 
Se hipoteticamente atribuíssemos para operações simples como atribuições, somas, 
multiplicações, etc., o valor de 01 unidade de tempo, o valor assintótico deste 
algoritmo, seria algo em torno de 6n+4, ou seja, uma equação linear, portanto O(n). 
 
Tentar atribuir um valor com exatidão, como foi o caso do pseudocódigo anterior, 
nem sempre é possível, por isso como mencionado anteriormente, a Análise 
Assintótica não procura mostrar o número exato de passos ou tempo que um 
algoritmo levará para executar determinada tarefa, mas sim o valor assintótico do 
mesmo quando o valor da entrada dos dados (n) variar ou tender ao ∞(infinito). 
 
Quando passamos a analisar o valor da entrada (n) em sua forma assintótica 
(tendendo ao infinito) dentro de, por exemplo, a denotação O, podemos ter com mais 
clareza a velocidade, ou melhor, tempo de resposta de um determinado grupo de 
algoritmos. Não dependendo assim de fatores referentes à máquina (memória, 
compilador, processador, etc.). 
 
Para uma maior clareza, vamos pensar em dois algoritmos que servem para a 
mesma tarefa, onde o algoritmo A tem o tempo de resposta 350n + 550, e o 
algoritmo B 3n² + 20n + 3. A princípio, com entradas pequenas, o algoritmo B levará 
certa vantagem quanto ao A, ex: 
Valor de T(n) = 3; 
A = 350 * 3 + 500 = 1550; O(n) 
B = 3*3² + 20 * 3 + 3 = 90; O(n²) 
Mas quando pensamos no valor de (n) subindo assintóticamente, claramente o 
algoritmo A executará uma menor quantidade de tarefas para satisfazer todas as 
operações do algoritmo, ex: 
Valor de T(n) = 300; 
A = 350 * 300 + 500 = 105500; O(n) 
B = 3 * 300² + 20 * 300 + 3 = 276003; O(n²) 
 
38 
 
Ainda observando os exemplos acima, pode-se notar que um algoritmo de equação 
linear sempre será mais rápido que um algoritmo quadrático, pois em algum ponto 
(n0) o algoritmos quadrático ultrapassará o linear, assim como um O(log(n)) será 
mais rápido que um linear. E também é válido dizer que, a análise assintótica 
dispensa os termos de menor valor, pois os mesmos não influenciam de maneira 
significativa no resultado final. Sendo assim, em um algoritmo de equação 5n² + 20n 
+ 6, somente será levado em consideração o maior termo, no caso 5n², logo teremos 
a denotação O(n²) para tal algoritmo. 
 
 A figura 15.0 mostra com mais clareza como algoritmos de diferentes notações se 
comportam quando a entrada (n) é variada, independentemente se o computador 
que o algoritmo de maior ordem esteja rodando seja algumas vezes mais rápido que 
o outro algoritmo. Neste exemplo, pode-se observar que, em algum ponto quando a 
marca do n0 é assintoticamente alta, o algoritmo de proporção f(n) passa ser a 
melhor escolha. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 15.0: Análise Assintótica 
Fonte: GOODRICH, TAMASSIA. Estrutura de dados e algoritmos em Java. 4. ed. ( 2007). 
 
É válido ressaltar que, dependendo do tamanho da entrada e a forma como a 
mesma é inserida, muitas vezes poderemos optar por um algoritmo de ordem maior, 
pois seu rendimento inicial, quando o valor de n ainda é pequeno, ou seja, não 
atingiu o ponto n0, pode ser mais rápido que o algoritmo de menor ordem. 
 
 
39 
 
2.4.2 PROGRAMAÇÃO LINEAR 
 
Segundo Gomes e Ribeiro (2004, p. 59) “a programação linear lida basicamente com 
o problema de alocar recursos escassos a atividades que por eles “competem” entre 
si, e cujo modelo se representa por meio de expressões lineares”. 
 
Uma observação válida é que, o termo programação, não diz respeito à 
programação de computadores, mas sim a planejamento, estrutura de ajuda a 
decisões, como alocar melhor os recursos disponíveis. 
 
Como base para uma melhor compreensão, será abordado um caso hipotético onde 
uma Empresa pretende otimizar sua produção mensal de cadeiras e mesas, 
visando, logicamente, diminuir seus custos e maximizar os lucros. Sabendo-se que, 
cada mesa precisa de 6 horas de carpintaria e 4 horas de pintura, as cadeiras 
precisam de 4 horas de carpintaria e 2 horas de pintura. Durante o período 
analisado, há disponível 240 horas-homem de carpintaria e 100 horas/homem de 
pintura. Cada mesa lucra R$ 7,00 e cada cadeira R$ 5,00. 
 
Montando os dados em uma tabela temos: 
 Horas para produzir 01 unidade 
Departamento Mesas (M) Cadeiras (C) 
Horas 
disponíveis 
Carpintaria 6 4 240 
Pintura 4 2 100 
 
Lucro unitário 7 5 
Tabela 3.0 – Exemplo PL 
Fonte: Adaptado pelo autor 
 
Depois de modelados os dados em uma tabela e já sabermos o que a empresa 
procura (otimizar custos e maximizar lucros), temos de observar os recursos 
escassos ( horas disponíveis). 
Agora é necessário observar, qual produto deverá ser utilizado, produzido, em 
detrimento de outro. Exemplo será que devemos produzir mais mesas? Isso 
40 
 
consequentemente exigiria mais madeira e tempo, o que deixaria as mesas com 
menor uso de tais recursos. 
Segundo Chase, Jacob e Aquilano (2006, p. 665) “quando um único objetivo deve 
ser maximizado (como o lucro) ou minimizado (como os custos), pode-se utilizar a 
programação linear”. 
 
Utilizando a formula para Maximizar (Z = C1X1 + C2X2 + ... + CnXn ou 
) e aplicando os dados informados pelo problema, obteremos o 
valor de Z (Maximização dos lucros), logicamente substituindo os valores de C1X1 ... 
pelos valores reais de cadeiras (C) e mesas (M). 
Logo a função para maximização seria 7M + 5C, ou seja, a quantidade de mesas x 
R$ 7,00 + a quantidade de cadeiras x R$ 5 reais. 
 
Observando as restrições implícitas pelo problema (tempo de carpintaria 240h, 
tempo de pintura 100h), sabemos que, cada mesa gasta 6h e cada cadeira 4h, logo 
temos a inequação de 6M + 4C <= 240. Fazendo o mesmo processo para a pintura, 
temos a inequação 4M + 2C <= 100. 
 
Conclui-se portanto que, para todo M,C >= 0, focando a maximização dos lucros 7M 
+ 5C, temos as restrições 6M + 4C <= 240 e 4M + 2C <= 100. Resolvendo assimde 
forma linear o problema. 
 
Imaginando um quadro também hipotético, onde precisaríamos modelar um cenário 
de mapa rodoviário onde sua estrutura construída em grafos pode ser de proporções 
gigantescas, e a necessidade de aplicar isso em um espaço ou tela de forma 
otimizada, priorizando algo (qualidade da imagem, por exemplo) e observando as 
restrições (tamanho da tela), o estudo desta resposta pela programação linear se 
torna algo interessante. 
 
Resumindo, como relata Chase, Jacob e Aquilano (2006, p. 665) “a programação 
linear reúne às várias técnicas matemáticas utilizadas para alocar os recursos 
limitados entre as demandas competitivas de uma maneira ótima”. 
 
 
41 
 
2.4.3 ALGORITMO ESCOLHIDO 
 
A tabela 3.0 descreve o tempo de resposta (complexidade algorítmica) dos 
algoritmos pesquisados para a conclusão da referente pesquisa. 
AUTORES DESCRIÇÃO COMPLEXIDADE 
Bellman-Ford 
Algoritmo utilizado em 
buscas de menor 
caminho, diferenciado 
pois aceita pesos 
negativos nas arestas. 
O(va) 
Floyd-Warshall 
Algoritmo utilizado em 
buscas de menor caminho 
em grafos orientados e 
valorados. 
O(n³) 
Dijsktra 
Algoritmo utilizado em 
buscas de menor caminho 
em uma rota, partindo de 
um ponto qualquer, sendo 
considerado um algoritmo 
guloso. 
O(n²) 
 
Tabela 4.0 – Complexidade dos algoritmos 
Fonte: Adaptado pelo autor. 
 
Com base nas informações adquiridas através das pesquisas realizadas para este 
projeto, foi utilizado para a conclusão do mesmo o algoritmo de Dijkstra. O qual 
melhor se enquadra para resolução do problema proposto por esta pesquisa, visto 
que, o algoritmo trabalha com pesos positivos nas arestas dos grafos, e tem uma 
resposta mais rápida (O(n²)) quando se comparado aos demais algoritmos 
abordados neste projeto. 
 
 
 
 
42 
 
2.5 FERRAMENTAS (IDE’s) E LINGUAGEM UTILIZADAS NO 
DESENVOLVIMENTO DO SOFTWARE 
 
 
2.5.1 C# 
 
O C# (leia-se Cê charp ou C Sharp) é uma linguagem orientada a objetos criada 
pela Microsoft (baseada nas linguagens C, C++ e Java), trabalha juntamente com 
sua plataforma .Net. 
 
Sharp (2008) relata que o C# é uma poderosa linguagem orientada para 
componentes da Microsoft, e que para um usuário com alguma experiência em 
outras linguagens orientadas a objetos como C++ e Java, a sua assimilação com a 
sintaxe e com o modo de trabalhar com a mesma será rápida. 
 
O protótipo foi desenvolvido com a utilização da linguagem C# juntamente com o kit 
de desenvolvimento Microsoft Visual C# 2008 Express (kit gratuito de 
desenvolvimento de aplicativos, criado pela Microsoft, com o intuito de auxiliar os 
programadores que trabalham com a linguagem C#). 
 
A escolha desta linguagem e IDE para o desenvolvimento do aplicativo se dá pelo 
fato de as mesmas terem sido usadas em algumas disciplinas estudadas durante a 
graduação. 
 
 
2.5.2 UML - UNIFIED MODELING LANGUAGE OU LINGUAGEM DE MODELAGEM DE DADOS 
 
Para uma melhor visualização de algumas funções e operações do software 
desenvolvido nesta pesquisa, foi utilizada como técnica de modelagem dos dados a 
UML. 
Segundo Booch, Rumbauch e Jacobson (2005, p. 13), “a UML, Linguagem Unificada 
de Modelagem, é uma linguagem gráfica para visualização, especificação, 
construção e documentação de artefatos de sistemas complexos de software”. 
43 
 
Booch, Rumbauch e Jacobson (2005), descrevem que a UML surgiu por volta da 
metade da década de 90, quando Booch, Jacobson e Rumbauch, perceberam que 
seus trabalhos anteriores (Rational Software Corporation, Objectory e General 
Electrics) estavam interligados de forma natural e progressiva, só lhes restando 
assim, juntarem os esforços e abstraírem o melhor de cada ideia. 
 
44 
 
3.0 IMPLEMENTAÇÃO DIJKSTRA – PROTÓTIPO 
 
 
3.1 DIAGRAMA DE CASO DE USO 
 
Segundo Medeiros(2004), um caso de uso é uma representação de diversas, 
variadas ações, as quais representam uma macroatividade. 
 
A figura 16.0 mostra com um caso de uso, uma visão macro do Protótipo criado 
nesta pesquisa. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Figura 16.0 – Diagrama de Caso de Uso – Protótipo 
 Fonte: Adaptado pelo Autor. 
 
Como observado na figura 16.0, o funcionamento do software é bem simples e 
objetivo, buscando mostrar na prática, o funcionamento do algoritmo de Dijkstra. 
No primeiro processo o usuário irá indicar qual o tipo de grafo que o algoritmo 
deverá trabalhar, e isso também influenciará na forma como as pontas das arestas 
serão desenhadas pelo software. Em seguida o usuário irá criar as cidades (nós), 
depois estabelecer as ligações existentes entre as mesmas e o peso (a distancia) 
45 
 
nas arestas equivalentes entre um nó e outro. Após estes processos, deverá ser 
informado pelo usuário, o ponto de partida (origem) em que o algoritmo deverá 
começar a buscar as menores rotas, e por último, o usuário inicia o software, 
deixando todos os cálculos e processos necessários para obter a menor, ou melhor, 
rota, incumbidos ao programa, onde uma vez finalizados os processos, o software 
retornará, as menores distâncias entre todos os pontos do grafo, partindo do ponto 
de origem informado pelo usuário. 
 
 
3.1.2 DIAGRAMA DE ATIVIDADES 
 
Os diagramas de atividades tem basicamente por função, mostrar as execuções, 
tarefas e ou atividades que ocorrem entre uma atividade e outra. 
Para um melhor entendimento e compreensão de algumas funcionalidades do 
protótipo, foi elaborado um diagrama de atividades (figura 17.0), baseado no 
processo de executar o algoritmo de Dijkstra no software, onde após a inserção dos 
dados pelo usuário e acionado a funcionalidade do algoritmo, o mesmo começa a 
fazer uma varredura dos dados, analisando-os e checando possíveis erros nos 
dados inseridos, como peso negativo das arestas, falta de ligação entre os vértices 
(nós), quantidade de nós insuficientes. 
46 
 
 Figura 17.0 – Diagrama de Atividades – Executar Dijkstra 
 Fonte: Adaptado pelo autor 
 
 
3.1.3 DIAGRAMA DE SEQUÊNCIA 
 
Segundo Medeiros (2004, p. 147), 
 
este diagrama pode ser usado para mostrar a evolução de uma dada 
situação em determinado momento do software, mostrar uma dada 
colaboração entre duas ou mais classes e pode, também, ser usado para 
mostrar a tradução de um Caso de Uso desde a interação com o usuário até 
a finalização daquele dado processo. 
 
47 
 
A figura 18.0, ilustra o diagrama de sequência do processo de execução do 
algoritmo de Dijkstra. Onde o mesmo complementa o diagrama de atividades, 
proporcionando assim, um melhor entendimento deste processo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 18.0 – Diagrama de sequência 
Fonte: Adaptado pelo autor 
 
 
3.1.4 DIAGRAMA DE CLASSES 
 
Para representar as relações e os conceitos entre as classes que fazem parte de um 
sistema, dá-se a elaboração de um diagrama de classes. 
48 
 
O protótipo apresentado neste projeto foi desenvolvido utilizado programação 
orientada a objetos. Para um melhor acompanhamento e entendimento do código, 
foi criado o diagrama de classes de parte do código. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Figura 19.0 – Diagrama de classe 
 Fonte: Adaptado pelo autor 
 
 
3.2 GRAFO DE ESTUDOS – PROTÓTIPO 
 
A imagem a seguir mostra o grafo que está pré-fixado no código do programa, se 
baseando nele que foi testado, abordado e estudadoo funcionamento do algoritmo 
em questão (Dijkstra). 
49 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 20.0 – Grafo pré-disposto do protótipo 
Fonte: Adaptado pelo autor 
 
 
3.3 PROTÓTIPO 
 
A figura abaixo mostra a tela inicial do protótipo, onde tanto os dados de entrada, 
assim como os de respostas, serão mostrados. 
É nesta tela que todo o controle das informações que serão utilizadas (como tipo de 
grafo (direcionado ou não), forma como os dados serão inseridos, tipo de inserção 
de dados (manual ou não), etc.) é administrado. 
No lado direito, no pequeno espaço branco, abaixo do label Melhor caminho.:, serão 
mostrados os nomes das cidades que farão parte da menor rota do grafo elaborado. 
 
 
 
 
 
50 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Figura 21.0 – Protótipo – Tela Principal 
 Fonte: Adaptado pelo autor 
 
Na parte inferior da tela principal, é possível observar alguns botões, combobox, 
textbox e radiobuttons, onde que, para uma correta funcionalidade do software, é 
imprescindível que acha um controle correto sobre os mesmos. 
 
Figura 21.1 – Protótipo – Tela Principal – Parte inferior 
Fonte: Adaptado pelo autor 
 
Dentro de cada combobox está a lista de cidades que estão pré-dispostas no 
programa (figura 20.0), onde o usuário deverá selecionar uma cidade como origem e 
outra como destino. Depois de selecionadas as cidades o usuário deverá clicar no 
51 
 
botão Dijkstra para que o programa execute o algoritmo que fará a busca pela 
melhor rota entre as duas cidades selecionadas. 
 
O botão Habilitar forma manual (ver figura 21.1) quando pressionado, habilita a 
forma manual de inserção dos dados, onde fica por inteira responsabilidade do 
usuário que todos os dados inseridos, estejam de forma correta, para que não haja 
falha ou erros no processo de busca de menor rota. 
 
Após todos os processos de inserção de dados, (modo manual), e pressionado o 
botão Dijkstra, a parte branca da tela principal, deverá mostrar em cada nó, o valor 
do seu menor caminho entre ele e o nó principal (origem), isso acontece, pois como 
explicado anteriormente nesta pesquisa, o algoritmo de Dijkstra é um método 
guloso, ou seja, ele não calcula somente o melhor caminho entre dois pontos de um 
grafo, mas sim, o melhor caminho entre o nó principal e os demais nós do grafo, 
tornando assim, cada resultado apresentado nos nós, o melhor ou menor caminho 
existente. 
 
 
Figura 21.2 – Protótipo – Simulação entrada de dados manualmente 
Fonte: Adaptado pelo autor 
52 
 
3.3.1 IMPLEMENTAÇÃO DO ALGORITMO DE DIJKSTRA EM C SHARP 
 
O código abaixo é parte principal ou pelo menos um pedaço dela, do algoritmo 
responsável pela otimização da busca das menores rotas. O código está adaptado 
para a linguagem escolhida. Tomei o cuidado de comentar os passos envolvidos 
neste trecho do código, para uma melhor compreensão do mesmo. 
 
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Windows.Forms; 
 
namespace Dijkstra 
{ 
 class Dijkstra 
 { 
 //Variáveis (vetores) para armazenamento da distância e caminho de cada nó 
(vértice) 
 public double [] distancia; 
 public int [] caminho; 
 
 //Lista para armazenar os nós ainda não checados pelo algoritmo 
 private List<int> lista_nos = new List<int>(); 
 
 //Função de inicialização 
 public void Inicializar(int comeco, int tamanho) 
 { 
 distancia = new double[tamanho]; 
 caminho = new int[tamanho]; 
 
 for (int i = 0; i < tamanho; i++) 
 { 
 distancia[i] = Double.PositiveInfinity; //Preenchendo com valores positivos 
"infinitos" 
 
 lista_nos.Add(i); //Adicionando nós na lista ^^ 
 
 } 
 
 /*Aqui, estou colocando o valor 0(zero) para o ponto inicial 
 e nulo (-1) para os caminhos anteriores */ 
 distancia[comeco] = 0; 
 caminho[comeco] = -1; 
 
 } 
 
53 
 
 private int proximoVertice() 
 { 
 double min = Double.PositiveInfinity; 
 int Vertex = -1; 
 
 //Procurando na lista pelas menores rotas (pesos nas arestas) 
 foreach (int j in lista_nos) 
 { 
 if (distancia[j] <= min) 
 { 
 min = distancia[j]; 
 Vertex = j; 
 } 
 } 
 
 lista_nos.Remove(Vertex); // Retira da lista o menor vértice encontrado 
 
 return Vertex; // Retorna o vértice de menor valor encontrado naquela busca 
 
 } 
 
 //Método construtor 
 public Dijkstra(double[,] G, int comeco) 
 { 
 int pNegativos = 0; 
 
 //Só pra nível de observação, para não dá erro no algoritmo 
 //... verificando se o grafo contém algo, 
 //e se contém pelo menos 2 vértices (Matrix de adjacencia ...então N x N ... 
colunas = linhas) 
 if (G.GetLength(0) < 1 || G.GetLength(0) != G.GetLength(1)) 
 { 
 MessageBox.Show("Erro no gráfico", "Error", MessageBoxButtons.OK, 
MessageBoxIcon.Error); 
 
 } 
 else 
 { 
 int tamanho = G.GetLength(0); //Instancio o tamanho que deverá ter os 
meus vetores (caminho e distancia) 
 
 Inicializar(comeco, tamanho); 
 
 
 while (lista_nos.Count > 0) 
 { 
 int u = proximoVertice(); 
 
 /* Laço inicial para a busca das conecções dos vértices */ 
 for (int v = 0; v < tamanho; v++) 
54 
 
 { 
 /* Checando se tem pesos negativos ligados nos vértices */ 
 if ((G[u, v] < 0) && (pNegativos == 0)) 
 { 
 MessageBox.Show("O Grafo contém pesos negativos", "Erro - 
Pesos Negativos", MessageBoxButtons.OK, MessageBoxIcon.Error); 
 pNegativos = 1; 
 } 
 
 /* Verifica se existe alguma ligação (aresta) entre os nós em 
questão*/ 
 if ((G[u, v] > 0) && (pNegativos == 0)) 
 { 
 /* Se existir, fazer o relaxamento da aresta*/ 
 if (distancia[v] > distancia[u] + G[u, v]) 
 { 
 distancia[v] = distancia[u] + G[u, v]; 
 caminho[v] = u; 
 } 
 } 
 } 
 } 
 } 
 
 } 
 
 } 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
55 
 
4.0 CONCLUSÃO E RECOMENDAÇÕES 
 
 
4.1 CONCLUSÃO 
 
Diminuir custos e aumentar a velocidade das respostas são fatores constantemente 
analisados e trabalhados para obtenção de êxito em ambos. 
Em problemas de menor caminho entre dois pontos de um grafo valorado, com 
pesos apenas positivos, observou que o algoritmo de Dijkstra juntamente com a 
linguagem C#, obteve o desempenho, por esta pesquisa, esperado. 
 
Após pesquisar e analisar os valores assintóticos de vários algoritmos, e colocar em 
prática o qual se mostrou o melhor (algoritmo de Dijkstra), foi constato que a 
utilização de algoritmos que trabalham com grafos, traz um desempenho favorável. 
É nítida a otimização de tempo nas respostas. 
 
Empresas de transportes, autônomos,taxistas e afins, que trabalham no ramo de 
transportes e fretes, trabalhando com softwares do mesmo gênero, poderiam 
diminuir os custos com combustível, pois saberiam antes da jornada de trabalho, o 
menor caminho a seguir. 
 
 
4.2 RECOMENDAÇÕES 
 
Recomendo que este projeto seja trabalhado mais amplamente, podendo o mesmo 
ser migrado para plataformas Mobiles, onde suas atualizações poderiam ser feitas 
através de uma base de dados, a qual conteria informações de diversas cidades e 
suas distancias entre si. Também tendo uma opção onde o usuário entraria com a 
informação do consumo do seu automóvel (Km/l), e ao final do processo, o software 
além de trazer a menor rota, também indicaria quantos litros de combustível, 
aproximadamente, o usuário iria gastar naquela viagem. Trazendo assim um 
conforto e praticidade aos profissionais do ramo de transporte (taxistas, autônomos, 
etc.). Pois o funcionamento desde protótipo, não se baseia em como chegar a um 
56 
 
determinado local, mas sim, quais são os melhores ou menores caminhos a seguir 
para chegar lá. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
57 
 
5.0 REFERÊNCIAS BIBLIOGRÁFICAS 
 
1. ANDRADE, Maria Margarida de. Introdução à metodologia do trabalho 
científico: elaboração de trabalhos na graduação. 5. ed. São Paulo: Atlas, 2001. 
 
2. BAJPAI, Avi C.; MUSTOE Leslie R.; VALKER, Dennis. Matemática para 
engenheiros. São Paulo: Hemus-Livraria Editora Ltda. 1980. 
 
3. BONCHEV, Danail; ROUVRAY, Denni H. Chemical Graph Theory: 
introduction and fundamentals. 1. ed. Amsterdam: Gordon and Breach Science 
Publishers S.A, 1991. 
 
4. CHASE, Richard B.; JACOBS F. Robert; AQUILANO, Nicholas J. 
Administração da produção para a vantagem competitiva. Porto Alegre: 
Bookman, 2006. 
 
5. DEWDNEY, A.K. 20.000 léguas matemáticas: um passeio pelo misterioso 
mundo dos números / A.K. Dewdney. Rio de Janeiro: Jorge Zahar Ed., 2000. 
 
6. GIL, Antonio Carlos. Como Elaborar Projetos de Pesquisa. 4.ed. São Paulo: 
Atlas,2007. 
 
7. GOLDBARG, Marco Cesar; LUNA, Henrique Pacca L. Otimização 
combinatória e programação linear. 2. Ed. Rio de Janeiro: Elsevier, 2005. 
 
8. GOMES, Carlos Francisco Simões; RIBEIRO, Priscila Cristina Cabral. Gestão 
da Cadeia de Suprimentos integrada à Tecnologia da Informação. São Paulo : 
Pioneira Thomson Learning, 2004. 
 
9. GOODRICH, Michael T; TAMASSIA, Roberto. Estrutura de dados e 
algoritmos em Java. 4. ed. – Porto Alegre : Bookman, 2007. 
58 
 
10. GOODRICH, Michael T; TAMASSIA, Roberto. Projeto de Algoritmos: 
Fundamentos, análise e exemplos da Internet. Porto Alegre: Bookman 
CompanhiaEd, 2004. 
 
11. MARIANI, Antonio Carlos. Livro eletrônico: Algoritmo de Dijkstra para cálculo 
do Caminho de Custo Mínimo. Disponível em 
http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html (Acessado em maio de 
2012). 
 
12. MEDEIROS, Ernani Sales de. Desenvolvendo software com UML 2.0: 
definitivo. São Paulo: Pearson Makron Books, 2004. 
 
13. MEDINA, Marco; FERTIG, Cristina. Algoritmos e programação: teoria e 
prática. São Paulo: Novatec Editora, 2006. 
 
14. MERTENS, Roberto S. Kahlmeyer; FUMANGA, Mario; TOFFANO, Claudia 
Benevento; SIQUEIRA, Fabio. Como elaborar projetos de pesquisa: Linguagem e 
método. 1. ed. Rio de Janeiro: FGV, 2007. 
 
15. OLIVEIRA, Tereza Farias de; NUNES, Márcia Vidal. Cidadania e cultura 
digital: apropriações populares da Internet. Rio de Janeiro: E-papers, 2011. 
 
16. REIS, Linda G. Produção de monografia da teoria à prática / Linda G. Reis. 
2. ed.Brasília : Senac-DF, 2008. 
 
17. RICHARDSON, Robert Jarry. Pesquisa social: métodos e técnicas. São 
Paulo:Atlas, 1999. 
 
18. SAID, Ricardo. Curso de Lógica de Programação. São Paulo: Digerati 
Books, 2007. 
 
19. SHARP, John. Microsoft Visual C# 2008: passo a passo / John Sharp. Porto 
Alegre : Bookman, 2008. 
59 
 
20. VERGARA, Sylvia Constant. Projetos e relatórios de pesquisa em 
administração. 4. ed. São Paulo: Atlas, 2003. 
 
21. ZIVIANE, Nivio. Projeto de algoritmos: com Implementações em Pascal e C. 
2. ed. rev. e ampl. São Paulo: Pioneira Thomson Learning, 2005.