Планируете автомобильное путешествие или пеший туристический маршрут? Вам снова на помощь придёт математика. Сегодня я расскажу Вам без излишней строгости о замечательном алгоритме поиска кратчайшего пути — алгоритме Дейкстры, который, кстати, еще многие проходили в школе. Поехали!
Эдсгер Дейкстра. Источник: https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Edsger_Wybe_Dijkstra.jpg/800px-Edsger_Wybe_Dijkstra.jpg
Итак, алгоритм Дейкстры работает на т.н. взвешенных графах — совокупности вершин, связанных между собой ребрами, каждому из которых присвоен определенный вес. Это вес может быть значением в км расстояния между городами, стоимостью перелетов между аэропортами и т.д.
Например, пусть на рисунке ниже каждой вершине соответствует город, а весам ребер — расстояние между городами в километрах. Наша задача найти кратчайшие маршруты с первого города во все остальные:
Алгоритм начинается с того, что первому городу присваивается метка "0", а остальным метка "бесконечность". Затем происходит перемещение из первого города во все смежные с ним города:
Например, из первого города едем во второй: длина маршрута равна "2", что меньше "бесконечности", поэтому присваиваем второму городу метку "2". Аналогично для четвертого и шестого городов — метки "4" и "8".
Посещенную вершину зачеркиваем, чтобы не путаться. В алгоритме это реализуется присваиванием вершине флага "1". Едем дальше и рассматриваем четвертую вершину:
Из четвертой вершину можно приехать в шестую. Складываем метку четвертой вершины ("4") и длину маршрута до шестой: 4 + 5 = 9 > 8, следовательно метку шестой вершины не меняем. Из четвертой вершины есть маршрут и седьмую: присваиваем её метку "15". Больше идти некуда — вычеркиваем. Отправляем во вторую вершину:
Из неё можно приехать в пятую (2 + 10 = 12) и в третью (2+3=5) вершины. Вычеркиваем и отправляемся дальше в третью:
Из неё дорога в пятую ( 5 + 9 =14 >12 ) и в шестую (5 + 4 = 9 > 8), а значит ни одна из меток не меняется. Вычеркиваем третью и рассматриваем оставшиеся две вершины: пятую и шестую.
В случае маршрута из пятой в седьмую вершину, метка последней изменяется, т.к. 12 + 2 < 15. В итоге получаем следующий набор маршрутов:
- 1 — 2 : 2
- 1 — 3 : 5
- 1 — 4 : 4
- 1 — 5: 12
- 1 — 6: 8
- 1 — 7: 14
Конечно, приведенный граф достаточно тривиален: для него кратчайшие маршруты можно определить на "глазок". А что, когда дело касается действительно масштабных карт?
******************************************************************************
И ещё, уважаемые Читатели, наверняка, у вас есть дети или внуки, которых не удивишь красивыми алгоритмами, потому что гаджеты давно заменили им традиционные игры и интересы. Для тех, кому знакома эта проблема, советую направить любовь ребенка к играм в полезное русло, заинтересовав, например, программированием.
В школе цифровых навыков Kodland есть курсы по созданию сайтов, игр, мультфильмов — каждому ребёнку будет интересно. Записать ребёнка на бесплатный урок (!) можно по этой ссылке. Рекомендую!
