City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Engineering shortest path algorithms
Saint Petersburg / autumn 2016, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Курс даёт уникальную возможность познакомиться с методологией разработки прикладных алгоритмов на конкретной задаче поиска кратчайших путей в дорожных сетях. В ходе курса будут изучаться и реализовываться алгоритмы, используемые миллионами людей в таких сервисах, как Google/Bing/Yandex карты. Предварительный план курса:

  1. Введение в методологию разработки прикладных алгоритмов.
  2. Алгоритм Дейкстры. Двунаправленный алгоритм Дейкстры.
  3. Алгоритм флагов на ребрах.
  4. Алгоритм контракционной иерархии.
  5. Алгоритм меток хабами.
  6. Кратчайшие пуи в условиях динамических изменений графа.
  7. Задача поиска кратчайшего пути от нескольких вершин к нескольким.
Для получения аттестации по курсу необходима реализация графовой структуры данных на языке C++, алгоритма Дейкстры, двунаправленного алгоритма Дейкстры, алгоритма флагов на ребрах и контракционной иерархии.