Кратчайший путь в ориентированном невзвешенном графе с критерием выбора между несколькими кратчайшими путями?

Question

Я ищу лучший способ решить эту вариацию для задачи кратчайшего пути:

У меня есть ориентированный граф с невзвешенными ребрами.Мне нужно иметь возможность найти кратчайший путь между любыми двумя узлами, если такой путь существует.Что отличает эту проблему от обычной проблемы кратчайшего пути, так это то, что: если существует несколько путей кратчайшей длины, мне нужно иметь возможность выбрать путь с наивысшим «авторитетом».

Каждый узел имеет числовые права доступа, а путь с наивысшими правами доступа - это просто путь с наибольшей суммой прав доступа узлов.

В итоге: Мне нужен самый короткийпуть между парой узлов в ориентированном графе, но если есть несколько путей с одинаковой минимальной длиной, мне нужно найти путь с наивысшим авторитетом пути.

Как лучше всего идтиделая это?Есть ли способ преобразовать это в взвешенный граф, а затем просто использовать алгоритм Дейкстры ?Есть ли способ изменить поиск в ширину , чтобы получить набор кратчайших путей, которые я затем могу перебрать, чтобы найти путь с наивысшим авторитетом?

Answer 1

Края невзвешенные, поэтому дайте каждому ребру вес 1+auth(v,u).[auth объясняется в следующей строке]

для каждого (v, u) набора auth(v,u) = max{authority} - authority(v) (*) [это верно, потому что, если вы используете ребро, выходящее из v, вы определенно посетили его].

(*) max{authority} является высшим авторитетом в графе.

нормализует ваш "рейтинг авторизации", поэтому Sigma(auth(v,u),for each (v,u) in E) < 1 [путем деления, так что авторитет граней все равно будетбыть пропорциональным оригиналу]

сейчас, запустите dijkstra на графике с новыми измененными весами.

Найденный кратчайший путь должен быть кратчайшим , потому что фактор авторитета не может преодолеть фактор расстояния, потому что он «слабый» [нормализован до менее 1].
И это тот, у которого наивысший authority [для вершин], поскольку он с самым низким auth [для ребер], поскольку он минимален.

Answer 2

Ничто в алгоритме Джикстры не заставляет вас использовать скаляр для представления стоимости пути.

Простая модификация состояла бы в том, чтобы использовать пару вместо одного значения, например (distance, authority) для представления стоимости пути. Порядок будет: < distance, затем > authority, то есть, чем ниже distance, тем выше приоритет, чем выше authority.