Как найти в неориентированном, взвешенном графике минимальный эйлеров путь? (Этот путь должен содержать заданные ребра)
Вес ребер является суммой двух точек (например: ребро 4-9 вес = 4 + 9 = 13) для всех ребер.
пример: с 6 узлами (N) и с 5 ребрами (E):
(1-5)
(6-1)
(5-5)
(2-4)
(2-4)
Решение: Мы должны добавить 2 ребра к минимальному эйлерову путю:
1-2
1-2
В этом примере 3-й узел изолирован, но это не проблема. Цель: путь Эйлера, содержащий все начальные ребра. В этом примере мы можем с 2 дополнительными ребрами (1-2) (1-2) путь Эйлера сделать: 5-> 5-> 1-> 2-> 4-> 2-> 1-> 6. Таким образом, мы посетили все начальные ребра с минимальными дополнительными ребрами, и мы используем все ребра только один раз.
Какой алгоритм лучше всего найти, когда 1<N,E<100000 и должен работать за 0,01 секунды?