Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями

• Определение эталонных программ для задач вычисления кратчайших путей.

• Обсуждение направлений будущих исследований в этой области, определение проблем, играющих важнейшую роль в решении реальных задач, для которых до сих пор не разработано эффективных решений.

Эталонный пакет входных данных также содержит генераторы запросов для задач нахождения [[Алгоритм поиска кратчайших путей с единственным источником|кратчайших путей с единственным источником]] либо поточечного вычисления кратчайших путей. В версии задачи с единственным источником источники выбираются случайным образом. В поточечной задаче рассматриваются как случайные, так и локальные запросы. Локальные запросы вида (s, t) генерируются посредством случайного выбора t среди вершин с рангом из интервала <math>[2^i, 2^{i + 1}) \;</math> согласно порядку сканирования вершин при помощи алгоритма Дейкстры с источником s для любого параметра i. Очевидно, что чем меньше величина i, тем ближе друг к другу в графе располагаются вершины s и t. Локальные запросы важны для проверки влияния расстояния между конечными точками запроса на эффективность работы алгоритмов.

   

== Экспериментальные результаты ==