Метод пометок (МП) или метод Дейкстры (Ху, 1974, гл.10) позволяет решить следующую задачу. Дан ориентированный граф, каждому ребру которого приписано положительное число (длина ребра). Требуется найти кратчайший путь от вершины <em>S</em> до вершины <em>F</em>. Если каждое ребро графа характеризуется не одной, а несколькими величинами, например, временем пути и его стоимостью, то невозможно однозначно указать наилучший путь из <em>S</em> в <em>F</em>, поскольку у разных лиц, принимающих решения (ЛПР), могут быть разные представления о сравнительной важности критериев. При этом необходимо требовать, чтобы найденный путь был оптимальным по Парето, т.е. не существовало пути, лучшего по всем критериям (Подиновский, Ногин, 1982, гл.1). Представляется естественной задача построения достаточно представительного множества Парето-оптимальных путей, из которого ЛПР сможет выбрать устраивающий его путь. Строить такое множество целесообразно с помощью интерактивной процедуры, постепенно уточняя требования ЛПР. В качестве основы для такой процедуры в работе (Белова, Заславский, 2020) был предложен следующий алгоритм. Будем искать путь, минимизирующий один из критериев (назовем этот критерий временем) и удовлетворяющий заданным ЛПР ограничениям для остальных критериев. Пусть для <em>j</em>-го критерия (<em>j</em><em>=</em><em>1,…</em><em>n</em>) ЛПР задал в качестве максимального допустимого значения <em>C</em>_<em>j</em>_<em>0</em>. В отличие от классического алгоритма МП вершина графа может получить не одну, а несколько пометок (<em>T</em>₁,<em>C</em>_<em>11</em>_,_…_,<em>C</em>_<em>n</em>_<em>1</em>),…,(<em>T</em>_<em>k</em>,<em>C</em>_<em>1</em>_<em>k</em><em>,</em><em>…</em><em>,</em><em>C</em>_<em>nk</em>), где <em>T</em>₁<…<<em>T</em>_<em>k</em> . Кроме того, пометки могут не только добавляться, но и удаляться. Приведем формальное описание алгоритма. <strong>Шаг 0. </strong>Присвоим вершине <em>S</em> постоянную пометку (0,0,…,0), а остальным вершинам временные бесконечные пометки. <strong>Шаг 1. </strong>Пусть <em>V</em>— последняя вершина, получившая постоянную пометку (<em>T</em>,<em> </em><em>C</em>_<em>1</em>_,_…_,<em>C</em>_<em>n</em>). Для каждой вершины <em>i</em>, в которую ведет ребро из <em>V</em>, вычислим величины <em>T</em>’_<em>i</em>=<em>T</em>+<em>t</em>_<em>i</em>, C’_<em>ji</em><em>=</em><em>C</em><em>+</em><em>C</em>_<em>ji</em><em>,</em>где <em>t</em>_<em>i</em><em>, </em><em>c</em>_<em>ji</em> — время и значение <em>j</em><em>-</em>го критерия, соответствующие ребру <em>V</em> – <em>i</em>. <strong>Шаг 2. </strong>Если не существует вершины <em>i</em>, для которой C’_<em>ji</em><em> </em><em>C</em>_<em>j</em>_<em>0</em>_{<em> </em>}(<em>j</em><em>=</em><em>1,…</em><em>n</em>), удаляем пометку (<em>T</em>,<em>C</em>) и переходим к шагу 4. <strong>Шаг 3. </strong>Сравниваем вектор ([[[image2]]],C’_<em>1</em>_<em>i</em><em>,</em><em>…</em><em>,</em> C’_<em>ni</em>) со всеми пометками (<em>T</em>_<em>k</em>,<em>C</em>_<em>k</em>_<em>1</em><em>,</em><em>…</em><em>,</em><em>C</em>_<em>kn</em>), присвоенными вершине <em>i</em>. Если для некоторого <em>k</em><em> </em><em>T</em>_<em>k</em>[[[image3]]]и <em>C</em>_<em>k</em>_<em>j</em>C’_<em>ji</em>, новая пометка не записывается. В противном случае записываем новую пометку и удаляем все пометки (<em>T</em>_<em>j</em>,<em>C</em>_<em>j</em>) с <em>T</em>’_<em>i</em><em> </em><em>T</em>_<em>k</em>_{<em> </em>}и C’_<em>ji</em><em> </em><em>C</em>_<em>k</em>_<em>j</em> <strong>Шаг 4. </strong>Если не существует ни одной временной пометки с C’_<em>ji</em><em> </em><em>C</em>_<em>j</em>_<em>0</em>_{<em> </em>}(<em>j</em><em>=</em><em>1,…</em><em>n</em>), то алгоритм заканчивает работу (т.е. не существует пути, удовлетворяющего заданному ограничению по стоимости). В противном случае находим пометку с наименьшим <em>T</em> и делаем ее постоянной. <strong>Шаг 5. </strong>Если вершина, получившая постоянную пометку, совпадает с <em>F</em>, строим обратным ходом искомый путь. Иначе возвращаемся к шагу 1.

<strong>Описание вычислительного эксперимента. </strong>Для проверки эффективности предложенного алгоритма использовался следующий метод генерации графов. Между вершинами <em>S</em><em> </em>и<em> </em><em>F</em><em> </em>располагаются <em>N</em> уровней по <em>K</em><em> </em>вершин на каждом, вершины <em>S</em><em> </em>и<em> </em><em>F</em><em> </em>соединяются со всеми вершинами ближайших к ним уровней. Между любыми двумя вершинами, лежащими на соседних уровнях, проводится ребро с вероятностью <em>p</em>_<em>1</em><em>, </em>а между двумя вершинами, лежащими через уровень, --- с вероятностью <em>p</em>_<em>2</em><em>. </em> После этого выбираются случайные значения весов ребер. В вычислительных экспериментах исследовалась зависимость эффективности алгоритма от значений <em>N</em><em>, </em><em>K</em><em>, </em><em>p</em>_<em>1</em><em>, </em><em>p</em>_<em>2</em><em>, </em>а также от наличия положительной или отрицательной корреляции между критериями. <strong>Результаты экспериментов</strong><strong>. </strong>В таблице 1 приведено время работы алгоритма при различных значениях <em>N</em><em> </em>и<em> </em><em>K</em><em> </em>для двух и трех критериев. Из таблицы видно, что для трех критериев алгоритм, как правило, работает дольше, чем для двух. Кроме того, можно сделать вывод, что наиболее существенное влияние на время работы алгоритма оказывает средняя длина <em>N</em><em> </em>путей между <em>S</em><em> </em>и <em>F</em><em>. </em>Например, время при <em>N</em><em>=5, </em><em>K</em><em>=100 </em>и <em>N</em><em>=100, </em><em>K</em><em>=5 </em>отличается примерно в 40 раз для двух и почти в 1000 раз для трех критериев, хотя общее количество вершин в обоих случаях одинаково. В таблице 2 приводится время работы алгоритма для двух критериев при наличии положительной и отрицательной корреляции между ними. Можно сделать вывод, что наличие положительной корреляции существенно уменьшает время работы алгоритма. Это связано с тем, что при отрицательной корреляции количество Парето-оптимальных путей существенно больше, а значит возрастает время проверки выполнения ограничений. В таблице 3 приводится время работы алгоритма в зависимости от вероятностей <em>p</em>_<em>1</em><em>, </em><em>p</em>_<em>2</em>_{<em> </em>}наличия ребер между соседними и несоседними уровнями. Видно, что время работы возрастает с ростом каждой из вероятностей. При этом влияние вероятности <em>p</em>_<em>1</em><em>, </em>оказывается выше. Это связано с ростом средней длины путей между <em>S</em><em> </em>и <em>F</em><em>.</em>