Задан неориентированный граф (в том числе может быть достаточно большим, скажем, миллион вершин и двадцать миллионов ребер), каждому ребру приписан положительный вес, выбраны две его вершины, A и B. Требуется найти простой путь (не содержащий циклов) от A до B, сумма весов ребер которого бы минимально (по сравнению со всеми другими возможными путями от A до B) отличалась от заданного числа L.
Кто-нибудь может посоветовать хороший алгоритм для решения задачи?
.png)
