Вершинами графа

Рассмотрим алгоритм решения для случая многомерного графа [5]. В конечном многомерном графе каждой дуге поставлено в соответствие число С_i_1,_i_2,,,_il_,_m_1,_m_2,,_ml, называемое длиной дуги из вершины x_i_1,_i_2,,_il в вершину x_m_1,_m_2,,_ml. Требуется найти путь наименьшей длины, ведущий из некоторой вершины S в некоторую вершину t. Для использования табличного представления многомерных матриц (пп. 1.4, 1.5) введем помечивание индексов C_i₁_,_i_{1 ,,}_m_{1 ,}_ml. Алгоритм включает в себя 3 шага.

Предварительный шаг. В табличном представлении матрицы C столбец помечается знаком *. Диагональному элементу в столбце , т.е. , придается значение . Помеченные вершины будем относить к множеству R, непомеченные – к , т.е. S Î R.

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

h_m_,_{l =}C _m _, _m₊ C_m_,l,

для чего входим в -строку и складываем диагональный элемент строки и элемент . Находим минимум , затем столбец l _i помечаем значением мультииндекса , а диагональному элементу столбца l _i придаем значение = . И так до тех пор, пока не пометим вершину t.

Заключительный шаг. Искомый путь определяем, двигаясь от t к S по отметкам вершин.

Рассмотренный алгоритм может использоваться для определения и наибольшего пути в многомерном ориентированном графе, если длину дуг C_i₁_,_i_{1 ,,}_m_{1 ,}_ml взять условно со знаком минус, а длину отсутствующих в графе дуг, как и ранее при поиске кратчайшего пути, брать равной бесконечности. Поиск наибольшего пути требуется, например, в задачах расчета сетевых графиков. Он носит название критического пути [4].

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