Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 11 - Coggle Diagram
Mapa Mental 11
Capítulo 9: "
Greedy Technique
".
Seção 9.3: "
Dijkstra's Algorithm
".
Aqui é considerado o
problema dos caminhos mais curtos de fonte única:
Partindo de um vértice chamado fonte em um grafo com peso conexo, é encontrada uma família de caminhos, em que cada um parte da fonte e vai para um vértice diferente do grafo.
O que tornou esse problema popular foi a variedade de aplicações práticas que ele possui.
Provavelmente, as aplicações mais usadas e óbvias são o planejamento de transporte e o roteamento de pacotes em redes de comunicação, incluindo a
Internet
.
Aplicações menos óbvias podem ser, dentre outros, encontrar o caminho mais curto em redes sociais e programação de tripulações de companhias aéreas.
Mesmo existindo vários algoritmos para encontrar os menores caminhos, mas aqui será considerado o melhor conhecido algoritmo para resolver o problema citado, o
algoritmo de
Djikstra
.
Ele é aplicável apenas para grafos com pesos não negativos direcionados e não direcionados.
O algoritmo encontra o caminho mais curto para um vértice do grafo em ordem de distância de uma determinada fonte.
Primeiramente, ele encontra o caminho mais curto da fonte até o vértice mais próximo a ela, depois até o segundo mais próximo, e assim em diante.
1 more item...
É bom ressaltar que os caminhos podem ter arestas em comum.