Алгоритм дейкстры и его реализация

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

Что такое математический граф

Считается, что понятие графа было введено в обиход в восемнадцатом веке Леонардом Эйлером. Именно он озвучил постановку и решение одной из классических задач этой теории – о семи мостах Кенигсберга. Для того чтобы объяснить объект этой теории, чаще всего пользуются такой аналогией, как передвижение между различными городами. Тогда граф на плоскости будет представлять собой всю схему маршрутов, где вершинами станут конкретные пункты (например, города), а ребрами – пути из одной вершины в другую (аналог дороги между городами). Алгоритм Дейкстры, кроме других способов, может дать решение этого вопроса.

Видео: Алгоритм Дейкстры

Нахождение кратчайшего пути

Одной из стандартных задач теории графов является та, в которой нужно определить оптимальный по затратам путь между двумя точками. Ее можно свести на плоскости к решению графа, в котором вершины – города - связаны между собой ребрами, что представляют собой возможные дороги. Причем каждая дорога имеет свою длину, следовательно, на проезд по ней придется потратить определенные средства. Эта сумма эквивалентна весу ребра на графе. Тогда задачу на практике можно сформулировать так: как проложить путь из одного города в другой, чтобы затратить на дорогу минимальные средства.

Видео: Информатика. Теория графов: Алгоритм Дейкстры. Центр онлайн-обучения «Фоксфорд»

Способы решения

Для решения этой задачи были придуманы некоторые алгоритмы, которые стали широко известны в научном мире. Например, алгоритм Флойда – Уоршелла, Форда – Беллмана. Классическим способом нахождения решения является также алгоритм Дейкстры. Он может использоваться и для взвешенного (известен вес каждого ребра) графа, и для разреженного. Для нахождения окончательного пути нужно проделать несколько шагов.

Алгоритм Дейкстры

Смысл этого способа заключается в том, что обходятся все вершины, начиная с заданной, при этом каждой присваивается метка с некоторым значением. Затем в результат войдут те вершины, метки которых минимальны. На первом шаге исходной вершине присваивается метка со значением 0. Затем рассматриваются все следующие вершины, то есть те, в которые можно попасть из исходной. Им присваиваются метки, значение которых определяется как сумма исходника и веса пути. Из вершин следующего шага выбирается та, что имеет наименьшее значение метки, и изучаются все вершины, в которые из нее можно пройти, не используя промежуточных вершин. Определяется новое значение метки, равное метке вершины – исходника плюс вес пути. Если полученное значение меньше, чем метка вершины, то метка изменяется. В противном случае остается исходное значение. При этом в отдельном массиве, размерность которого равна количеству вершин графа, сохраняется результат оптимизации, по которому и определяется путь. Для реализации такого способа, как алгоритм Дейкстры, Pascal предлагает очень удобные средства. Алгоритм имеет то преимущество, что легко может быть положен в основу программы, которая имеет небольшой размер. Примеры таких программных продуктов легко найти в сети Интернет.

Видео: BP2-3-2-07 Алгоритм Дейкстры

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