Рассмотрим алгоритм решения для случая многомерного графа [5]. В конечном многомерном графе каждой дуге поставлено в соответствие число Сi1,i2,,,il,m1,m2,,ml, называемое длиной дуги из вершины xi1,i2,,il в вершину xm1,m2,,ml. Требуется найти путь наименьшей длины, ведущий из некоторой вершины S в некоторую вершину t. Для использования табличного представления многомерных матриц (пп. 1.4, 1.5) введем помечивание индексов Ci1 ,i1 ,,m1 ,ml . Алгоритм включает в себя 3 шага.
Предварительный шаг. В табличном представлении матрицы C столбец помечается знаком *. Диагональному элементу в столбце , т.е. , придается значение . Помеченные вершины будем относить к множеству R, непомеченные – к , т.е. S Î R.
Общий шаг. Рассмотрим все дуги, исходящие из множества помеченных вершин R и заканчивающиеся на непомеченных вершинах . Для каждой дуги найдем
hm ,l =C m , m + Cm ,l ,
для чего входим в -строку и складываем диагональный элемент строки и элемент . Находим минимум , затем столбец l i помечаем значением мультииндекса , а диагональному элементу столбца l i придаем значение = . И так до тех пор, пока не пометим вершину t.
|
|
Заключительный шаг. Искомый путь определяем, двигаясь от t к S по отметкам вершин.
Рассмотренный алгоритм может использоваться для определения и наибольшего пути в многомерном ориентированном графе, если длину дуг Ci1 ,i1 ,,m1 ,ml взять условно со знаком минус, а длину отсутствующих в графе дуг, как и ранее при поиске кратчайшего пути, брать равной бесконечности. Поиск наибольшего пути требуется, например, в задачах расчета сетевых графиков. Он носит название критического пути [4].
Возможен и другой вариант нахождения наибольшего пути в ориентированном графе, не связанный с изменением «знака» длины дуг. Будем считать длину дуг положительными величинами. Тогда для получения наибольшего пути в ориентированном графе с помощью изложенного табличного алгоритма необходимо при определении находить не минимальное значение, а максимальное. Этот подход наиболее распространен в задачах сетевого планирования.