PatataSniper / Biklas_API_V2

REST API para aplicación Biklas en .NET 6
0 stars 0 forks source link

Investigar posibilidad de modificar algoritmo Dijkstra, implementado en Itinero #1

Closed PatataSniper closed 1 year ago

PatataSniper commented 1 year ago

Es necesario investigar la posibilidad de modificar el algoritmo Dijkstra, implementado por defecto en la biblioteca 'Itinero.Routes'. El objetivo es agregar valor sobre lo ya existente, en aras de cumplir con creces los requisitos del 2do módulo

PatataSniper commented 1 year ago

Podemos encontrar información, referente a la implementación del algoritmo Dijkstra, en el repositorio oficial de Itinero, Itinero.Routing. Como punto de partida se sugiere investigar dos sobrecargas de la función 'Calculate' y dos sobrecargas de la función 'TryCalculate' Ubicadas en el archivo 'RouterBaseExtensions' (compilado), ya que estas sobre cargas requieren de un parámetro de tipo 'IMassResolvingAlgorithm'

PatataSniper commented 1 year ago

Publicamos una pregunta en la plataforma Stack Overflow referente al funcionamiento interno de Itinero y sobre cual algoritmo utiliza por defecto. La solución fue encontrada (Itiniero utiliza Dijkstra bidireccional con un montón binario como cola de prioridad). Profundizar un poco más en las conclusiones y considerar responder yo mismo la pregunta en Stack Overflow.

PatataSniper commented 1 year ago

Referente a la pregunta ¿Por qué Itinero utiliza el algoritmo Dijkstra bidireccional en lugar de A*? Encontramos las siguientes fuentes: https://stackabuse.com/courses/graphs-in-python-theory-and-implementation/lessons/dijkstras-algorithm-vs-a-algorithm/