![\"\"](\"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide147.jpg?resize=960%2C720\")
<\/p>\n<\/p>\n
O conceito mais simples de caminho mais curto \u00e9 medir o comprimento do caminho atrav\u00e9s do n\u00famero de hops. Uma outra medida \u00e9 a dist\u00e2ncia geogr\u00e1fica em quil\u00f4metros. Entretanto, muitas outras unidades m\u00e9tricas s\u00e3o poss\u00edveis, por exemplo, o retardo m\u00e9dio de enfileiramento e de transmiss\u00e3o referente a um pacote de teste padr\u00e3o, de acordo com as especifica\u00e7\u00f5es de teste executados a cada hora. Nesse grafo, o caminho mais curto \u00e9 o caminho mais r\u00e1pido, e n\u00e3o o caminho com menor n\u00famero de arcos ou quil\u00f4metros.<\/p>\n
Existem v\u00e1rios algoritmos para se calcular o caminho mais curto entre dois n\u00f3s de um grafo. O algoritmo de Dijkstra (1959) \u00e9 um dos mais estudados. Nesse algoritmo cada n\u00f3 \u00e9 identificado (entre par\u00eanteses na figura) por sua dist\u00e2ncia a partir do n\u00f3 de origem ao longo do melhor caminho conhecido. Inicialmente, nenhum caminho \u00e9 conhecido; portanto, todos os n\u00f3s s\u00e3o rotulados com infinito. \u00c0 medida que o algoritmo prossegue e os caminhos s\u00e3o encontrados, os r\u00f3tulos podem mudar, refletindo melhores caminhos. Um r\u00f3tulo pode ser provis\u00f3rio ou permanente. No in\u00edcio, todos s\u00e3o provis\u00f3rios. Quando se descobre que um r\u00f3tulo representa o caminho mais curto poss\u00edvel at\u00e9 a a origem desse n\u00f3, ele se torna permanente e nunca mais \u00e9 alterado da\u00ed em diante.<\/p>\n
A figura acima mostra um grafo ponderado n\u00e3o-ponderado, onde os pesos representam a dist\u00e2ncia. Para encontrar o caminho mais curto de A at\u00e9 D, marca-se o n\u00f3 A como permanente, o que \u00e9 indicado por um c\u00edrculo preenchido. Depois examina-se separadamente cada um dos n\u00f3s adjacentes a A (o n\u00f3 ativo), alterando-se o r\u00f3tulo de cada um deles para indicar a dist\u00e2ncia at\u00e9 A. Sempre que um n\u00f3 \u00e9 rotulado novamente, ele tamb\u00e9m \u00e9 rotulado com o n\u00f3 a partir do qual o teste foi feito; assim, pode-se reconstruir o caminho final mais tarde. Ap\u00f3s examinar cada um dos n\u00f3s adjacentes a A, verifica-se todos os n\u00f3s provisoriamente rotulados no grafo inteiro e torna-se permanente o n\u00f3 que tem o menor r\u00f3tulo. Esse n\u00f3 passa a ser o novo n\u00f3 ativo.<\/p>\n
A partir de B pode-se examinar todos os n\u00f3s adjacentes a ele. Se a soma do r\u00f3tulo de B e a dist\u00e2ncia entre B e o n\u00f3 que est\u00e1 sendo considerado for menor que o r\u00f3tulo desse n\u00f3, define-se como o caminho mais curto; portanto, o n\u00f3 ser\u00e1 rotulado novamente. A figura acima mostra as cinco primeiras etapas do algoritmo.<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
O conceito mais simples de caminho mais curto \u00e9 medir o comprimento do caminho atrav\u00e9s do n\u00famero de hops. Uma outra medida \u00e9 a dist\u00e2ncia geogr\u00e1fica em quil\u00f4metros. Entretanto, muitas outras unidades m\u00e9tricas s\u00e3o poss\u00edveis, por exemplo, o retardo m\u00e9dio de enfileiramento e de transmiss\u00e3o referente a um pacote de teste padr\u00e3o, de acordo com […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":741,"menu_order":100,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-747","page","type-page","status-publish","hentry"],"jetpack_shortlink":"https:\/\/wp.me\/P8yKGp-c3","jetpack-related-posts":[{"id":758,"url":"https:\/\/efagundes.com\/networking\/algoritmos-de-roteamento\/roteamento-por-difusao\/","url_meta":{"origin":747,"position":0},"title":"Roteamento por difus\u00e3o","author":"Eduardo Fagundes","date":"18\/11\/2012","format":false,"excerpt":"Para algumas aplica\u00e7\u00f5es os hosts precisam enviar mensagens a muitos outros hosts. Um exemplo \u00e9 o servi\u00e7o de distribui\u00e7\u00e3o de relat\u00f3rios sobre o tempo, atualiza\u00e7\u00f5es do mercado de a\u00e7\u00f5es ou programas de r\u00e1dio ao vivo. O envio de um pacote a todos os destinos simultaneamente \u00e9 chamado difus\u00e3o (broadcasting). Um\u2026","rel":"","context":"Post similar","block_context":{"text":"Post similar","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide195.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide195.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide195.jpg?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide195.jpg?resize=700%2C400 2x"},"classes":[]},{"id":77,"url":"https:\/\/efagundes.com\/networking\/hardware-de-rede\/roteador-dedicado\/","url_meta":{"origin":747,"position":1},"title":"Roteador dedicado","author":"Eduardo Fagundes","date":"16\/11\/2012","format":false,"excerpt":"\u00a0 Em redes geograficamente distribu\u00eddas \u00e9 importante o conceito de roteamento. Entende-se por roteamento \u00e9 a escolha do m\u00f3dulo do n\u00f3 de origem ao n\u00f3 de destino por onde as mensagens devem transitar. Na comuta\u00e7\u00e3o de circuito, nas mensagens ou de pacote. Primeiramente estabelece uma conex\u00e3o entre n\u00f3s de origem\u2026","rel":"","context":"Post similar","block_context":{"text":"Post similar","link":""},"img":{"alt_text":"Slide13","src":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide13.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide13.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide13.jpg?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide13.jpg?resize=700%2C400 2x"},"classes":[]},{"id":753,"url":"https:\/\/efagundes.com\/networking\/algoritmos-de-roteamento\/roteamento-por-estado-de-enlace\/","url_meta":{"origin":747,"position":2},"title":"Roteamento por estado de enlace","author":"Eduardo Fagundes","date":"18\/11\/2012","format":false,"excerpt":"Estado de enlace: Tamb\u00e9m definido como algoritmo Link State, este algoritmo trabalha baseado na ideia de que cada roteador possui informa\u00e7\u00f5es sobre as redes que est\u00e3o conectadas a ele e, periodicamente, testa para determinar se cada enlace est\u00e1 ativo. Com estas informa\u00e7\u00f5es cada roteador divulga uma lista sobre o status\u2026","rel":"","context":"Post similar","block_context":{"text":"Post similar","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide175.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide175.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide175.jpg?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide175.jpg?resize=700%2C400 2x"},"classes":[]},{"id":751,"url":"https:\/\/efagundes.com\/networking\/algoritmos-de-roteamento\/roteamento-com-vetor-distancia\/","url_meta":{"origin":747,"position":3},"title":"Roteamento com vetor dist\u00e2ncia","author":"Eduardo Fagundes","date":"18\/11\/2012","format":false,"excerpt":"Os algoritmos de roteamento com vetor de dist\u00e2ncia operam fazendo cada roteador manter uma tabela (isto \u00e9,\u00a0 um vetor) que fornece a melhor dist\u00e2ncia conhecida at\u00e9 cada destino e determina qual linha deve ser utilizada para se chegar l\u00e1. Essas tabelas s\u00e3o atualizadas atrav\u00e9s da troca de informa\u00e7\u00f5es com os\u2026","rel":"","context":"Post similar","block_context":{"text":"Post similar","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide166.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide166.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide166.jpg?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide166.jpg?resize=700%2C400 2x"},"classes":[]},{"id":749,"url":"https:\/\/efagundes.com\/networking\/algoritmos-de-roteamento\/inundacao-flooding\/","url_meta":{"origin":747,"position":4},"title":"Inunda\u00e7\u00e3o (flooding)","author":"Eduardo Fagundes","date":"18\/11\/2012","format":false,"excerpt":"O algoritmo de inunda\u00e7\u00e3o (flooding) \u00e9 um algoritmo est\u00e1tico, no qual cada pacote de entrada \u00e9 enviado para todas as linhas de sa\u00edda, exceto para aquela que chegou. O algoritmo de inunda\u00e7\u00e3o gera uma vasta quantidade de pacotes duplicados, na verdade um n\u00famero infinito, a menos que algumas medidas sejam\u2026","rel":"","context":"Post similar","block_context":{"text":"Post similar","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide156.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide156.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide156.jpg?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide156.jpg?resize=700%2C400 2x"},"classes":[]},{"id":745,"url":"https:\/\/efagundes.com\/networking\/algoritmos-de-roteamento\/o-principio-de-otimizacao\/","url_meta":{"origin":747,"position":5},"title":"O princ\u00edpio de otimiza\u00e7\u00e3o","author":"Eduardo Fagundes","date":"18\/11\/2012","format":false,"excerpt":"\u00c9 poss\u00edvel criar uma descri\u00e7\u00e3o geral das rotas \u00f3timas sem levar em conta a topologia ou o tr\u00e1fego de rede. Essa descri\u00e7\u00e3o \u00e9 conhecida como princ\u00edpio de otimiza\u00e7\u00e3o. Esse princ\u00edpio estabelece que, se o roteador J estiver no caminho \u00f3timo entre o roteador I e o roteador K, o caminho\u2026","rel":"","context":"Post similar","block_context":{"text":"Post similar","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide137.jpg?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide137.jpg?resize=350%2C200 1x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide137.jpg?resize=525%2C300 1.5x, https:\/\/i0.wp.com\/efagundes.com\/networking\/wp-content\/uploads\/sites\/5\/2015\/03\/Slide137.jpg?resize=700%2C400 2x"},"classes":[]}],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/pages\/747","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/comments?post=747"}],"version-history":[{"count":0,"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/pages\/747\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/pages\/741"}],"wp:attachment":[{"href":"https:\/\/efagundes.com\/networking\/wp-json\/wp\/v2\/media?parent=747"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}