Найти минимальную стоимость эйлерова пути, содержащего заданные ребра в неориентированном графе (алгоритм)
Как найти в неориентированном взвешенном графе минимальный эйлеров путь?(Этот путь должен содержать заданные ребра)
Вес ребер равен сумме 2 баллов (например, вес ребра 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-й узел изолирован, но это не проблема. Цель: эйлеров путь, содержащий все начальные ребра. В этом примере мы можем с двумя дополнительными ребрами (1-2)(1-2) выполнить путь Эйлера: 5->5->1->2->4->2->1->6. Итак, мы посетили все Start-ребра с минимальным количеством дополнительных ребер и использовали все ребра только один раз.
Какой алгоритм лучше всего найти, когда 1<N,E<100000, и должен работать за 0,01 секунды?