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

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

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

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

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

Методы решения

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

Метод Дейкстры

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

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