Temas relacionados a la programación
Foto de Usuario
DiegoHDMGZ

Ranking Troomes
Mensajes: 8
Registrado: 18 Abr 2020, 17:33

Shortest Path Algorithms (BFS, Dijkstra y más)

Mensaje por DiegoHDMGZ » 02 Dic 2020, 01:08

El presente documento es una de las clases que dicto en el grupo de programación competitiva UNI, al ser yo uno de los coaches encargados. El tema aborda algoritmos que están relacionados al problema de encontrar la ruta más corta (shortest path) en un grafo.

El documento está en español y ha sido elaborado por mí, en su totalidad, e incluye los siguientes algoritmos:
  • BFS (Breadth First Search)
  • Programación dinámica para hallar shortest path en DAG
  • Dijkstra's Algorithm
  • Bellman-Ford Algorithm
  • Moore's Algorithm
  • Floyd-Warshall Algorithm
Cada uno de estos está acompañado de su respectiva demostración tanto de su correctitud como de su complejidad algorítmica. También están acompañados de códigos en C++.

Estos algoritmos son usados en los concursos de programación, pero también están presentes en algunos cursos de nuestra carrera como Investigación de operaciones II e Inteligencia Artificial Avanzada.

En particular, el algoritmo de BFS es visto también en el curso de IA Avanzada con el profesor Wester Zela. Mientras que el algoritmo de Dijkstra es visto en Investigación de Operaciones II (también es visto en IA avanzada, pero en su versión heurística como el algoritmo A*). Es por esa razón que creo que estos documentos pueden contribuir a profundizar un poco más sobre esos conceptos vistos en clase.
Adjuntos


Responder