4430
правок
Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями
Материал из WEGA
Конкурс по реализации алгоритмов поиска кратчайших путей (посмотреть исходный код)
Версия от 10:48, 4 июня 2018
, 4 июня 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей: | Участники конкурса изучали следующие варианты задачи нахождения кратчайших путей: | ||
• ''Поточечное вычисление кратчайших путей'' [4, 5, 6, 9, 10, 11, 14]: | • ''Поточечное вычисление кратчайших путей'' [4, 5, 6, 9, 10, 11, 14]: | ||
| Строка 29: | Строка 30: | ||
• ''Поиск кратчайших путей во внешней памяти'' [2]: | • ''Поиск кратчайших путей во внешней памяти'' [2]: | ||
Задача заключается в | Задача заключается в нахождении кратчайших путей в графе, размер которого слишком велик для хранения во внутренней памяти. Во время конкурса фактически решалась задача нахождения кратчайших путей с единственным источником в неориентированных графах с единичными весами ребер. | ||
| Строка 47: | Строка 48: | ||
Кульминацией конкурса стал семинар в центре DIMACS в Ратгерском университете в Пискатавэе, штат Нью-Джерси, проведенный 13-14 ноября 2006 года. Представленные на конференции доклады можно найти по адресу http://www.dis. uniroma1.it/~challenge9/papers.shtml. Избранные материалы вошли в книгу, опубликованную Американским математическим сообществом в серии DIMACS Book Series. | Кульминацией конкурса стал семинар в центре DIMACS в Ратгерском университете в Пискатавэе, штат Нью-Джерси, проведенный 13-14 ноября 2006 года. Представленные на конференции доклады можно найти по адресу http://www.dis.uniroma1.it/~challenge9/papers.shtml. Избранные материалы вошли в книгу, опубликованную Американским математическим сообществом в серии DIMACS Book Series. | ||
== Основные результаты == | == Основные результаты == | ||
