На черговому засіданні гуртка «Дискретні структури для програмістів» кафедри Інженерії програмного забезпечення учасники розглядали різні алгоритми мінімізації шляху в графах, використовуючи мови програмування.

Задача про  найкоротший  шлях  є  однією  з  найважливіших  класичних задач  теорії графів – задача  пошуку  короткого  шляху (ланцюга) між двома точками (вершинами) на графі, у якому мінімізується сума ваг ребер, що утворюють шлях. Відомо безліч алгоритмів для її вирішення. Важливість  даної  задачі  визначається  її  різними  практичними застосуваннями.  Наприклад  в  GPS-навігаторах,  де  здійснюється пошук найкоротшого шляху між двома точками на карті. В якості вершин виступають перехрестя, а дороги є ребрами, що їх сполучають. Сума відстаней всіх доріг між точками повинна бути мінімальною, тоді знайдено найкоротший шлях.

Існують різні постановки задачі про найкоротший шлях:

1. Задача про найкоротший шлях в заданий пункт призначення. Потрібно знайти найкоротший шлях в задану вершину призначення t, який починається в кожній з вершин графа (крім t).
2. Задача про найкоротший шлях між заданою парою вершин. Потрібно знайти найкоротший шлях із заданої вершини u в задану вершину v;
3. Задача про найкоротший шлях між усіма парами вершин. Потрібно знайти найкоротший шлях з кожної вершини u в кожну вершину v.

У різних постановках задачі, роль довжини ребра можуть грати не тільки самі довжини, але й час, вартість, витрати, обсяг витрачених ресурсів (матеріальних, фінансових, паливно-енергетичних і т. п.) або інші характеристики, пов'язані з проходженням кожного ребра. Таким чином, завдання знаходить практичне застосування у великій кількості областей (інформатика, економіка, географія та ін.)

До найбільш популярних алгоритмів пошуку маршруту в графі можна віднести: алгоритм Дейкстри, алгоритм Беллмана –Форда, алгоритм пошуку A*, який знаходить маршрут з найменшою вартістю від однієї вершини (початкової) до іншої (цільової, кінцевої), алгоритм Флойда-Уоршелла,  алгоритм Джонсона, алгоритм Лі (хвильовий алгоритм), Contraction hierarchies (алгоритм з переобробкою графу для знаходження коротших шляхів і «віртуального» видалення вершин які можна  пропустити при пошуку маршруту).

Студенти Пд-13, які є постійними учасниками гуртка, зосередили свою увагу на алгоритмі Флойда-Уоршела. Це динамічний алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа, який був розроблений в 1962 році Робертом Флойдом і Стівеном Уоршелом,  хоча в 1959  році Бернард Рой (Bernard Roy) опублікував практично такий самий алгоритм,  але це залишилося непоміченим.

Кирпичов Олександр на мові Javascript презентував наочне представлення алгоритму Флойда-Уоршела на прикладі потягів і станцій, як застосування алгоритму до знаходження мінімального шляху між станціями.

Успіх приходить до тих, хто займається улюбленою справою, а участь студентів 1 курсу в роботі гуртка підтверджує, що вибір зроблений вдало!

Запрошуємо випускників 11 класів відвідати наші гуртки, познайомитись зі студентами, поспілкуватись з викладачами та визначитись з майбутнім фахом!

Розклад гуртків за посиланням.