En este artículo se presenta el problema de la búsqueda de mejor camino como un problema de programación lineal, el cual puede ser resuelto por el método simplex. Sin embargo, por el tipo de restricciones que se manejan será aconsejable resolverlo por simplex dual o simplex dual-primal. Por otra parte, la complejidad de simplex es NP en el peor de los casos, por lo que no es conveniente usar este método en la vida real. Por lo tanto presento el algoritmo Dijkstra y muestro que es mucho mas efectivo su uso que el de Simplex. Al ser DIjkstra un algoritmo especializado para resolver estos problemas es aconsejable usarlo, u otro especializado. La instancia sobre la cual pruebo los dos algoritmos es la red del metro y metrobús de la ciudad de México. Espero sea de su interés. El PDF se phede desgargar aquí.

 

Descargar artículo.

Share This