Алгоритм определения кратчайших путей

Эта задача имеет большое значение в практических примене­ниях. К ней сводятся многие задачи выбора наиболее экономичного (с точки зрения расстояния или стоимости) маршрута на имеющейся карте дорог, наиболее экономичного способа перевода динамиче­ской системы из одного состояния в другое и т.д. Существует много математических способов решения, но часто методы, основанные на теории графов, наименее трудоемки.

Рассмотрим задачу о кратчайшем пути. Пусть дан граф G(X), ду­гам которого приписаны веса (расстояния, стоимости и т.п.), задаваемые матрицей С = || c_ij ||.

Задача о кратчайшем пути состоит в нахож­дении кратчайшего пути от заданной начальной вершины s Î X до заданной конечной вершины t Î X при условии, что такой путь су­ществует. В общем случае возможно С_ij > 0, С_ij < 0, С_ij = 0. Единст­венное ограничение состоит в том, чтобы в графе G(X) не было циклов с отрицательным суммарным весом.

Приведем очень простой и эффективный алгоритм Дейкстры решения этой задачи для случая С_ij ³ 0 " i, j. Алгоритм основан на приписывании вершинам временных пометок, причем пометка вер­шины дает верхнюю границу длины пути от s к этой вершине. Вели­чины этих пометок постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это означает, что по­метка уже не является верхней границей, а дает точную длину крат­чайшего пути от s к рассматриваемой вершине. Пусть l(x_i) – пометка вершины x_i. Опишем основные этапы алгоритма.