Encontrando o caminho mais curto com o algoritmo de Dijkstra

cupom com desconto - o melhor site de cupom de desconto cupomcomdesconto.com.br


Eu tenho que fazer uma confissão: no que diz respeito ao meu senso de orientação, sou um fracasso total … às vezes parece que o GPS e os mapas do Google foram inventados para mim!

Bem, hoje em dia qualquer um usa esses ajudantes práticos. Mas como eles conseguem encontrar o caminho mais curto de A para B?

Se você quiser entender o pai de todos os algoritmos de roteamento, Algoritmo de Dijkstra, e quero saber como programá-lo em R continue a ler!

Este post é parcialmente baseado neste ensaio Python Patterns – Implementing Graphs, o exemplo é do livro alemão “Das Geheimnis des kürzesten Weges” (“O segredo do caminho mais curto”) do meu colega Professor Gritzmann e Dr. Brandenberg. Para encontrar a maneira mais elegante de converter frames de dados em objetos igraph, recebi ajuda (mais uma vez!) Da maravilhosa comunidade R do StackOverflow.

O algoritmo de Dijkstra é um algoritmo recursivo. Se você não está familiarizado com recursão você pode querer ler meu post. Para entender a recursão, você precisa entender a recursão … primeiro.

Primeiro, vamos definir o gráfico em que queremos navegar e anexamos pesos pelo tempo que leva para cobri-lo. Usamos o excelente igraph pacote (no CRAN) para visualizar o gráfico:

cupom com desconto - o melhor site de cupom de desconto cupomcomdesconto.com.br
library(igraph)
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
graph 

Next, we create a helper function to calculate the path length:

path_length 

And now for the core of the matter, Dijkstra’s algorithm: the general idea of the algorithm is very simple and elegant: start at the starting node and call the algorithm recursively for all nodes linked from there as new starting nodes and thereby build your path step by step. Only keep the shortest path and stop when reaching the end node (base case of the recursion). In case you reach a dead-end in between assign infinity as length (by the path_length function above).

I added a lot of documentation to the code so it is hopefully possible to understand how it works:

find_shortest_path 

Now, we can finally test the algorithm by calculating the shortest path from s to z and back:

find_shortest_path(graph, "s", "z") # via b
## [1] "s" "b" "c" "d" "f" "z"

find_shortest_path(graph, "z", "s") # back via a
## [1] "z" "f" "d" "b" "a" "s"

Observe que as duas rotas são realmente diferentes por causa dos pesos diferentes em ambas as direções (por exemplo, pense em algum trabalho de construção em uma direção, mas não na outra).

Na próxima semana aprenderemos como Sistema de Posicionamento Global (GPS) funciona, fique atento!



cupom com desconto - o melhor site de cupom de desconto cupomcomdesconto.com.br
Leia Também  Animação de distribuições de população dos EUA