Кратчайшие два непересекающихся пути; два источника и два пункта назначения
Нам дан невзвешенный неориентированный графG = (В, Е)где |V| <= 40 000 и |E| <= 10 6. Нам также даны четыре вершины a, b, a', b' . Есть ли способ найти два узловых -непересекающихся пути a -> a' и b -> b' такие, что сумма их длин будет минимальной?
Моей первой мыслью было сначала найти кратчайший путь a -> a' , удалить его из графа, а затем найти кратчайший путь b -> b' . Не думаю, что этот жадный подход сработает.
Примечание:Во всем приложении a и b фиксированы, а a' и b' меняются при каждом запросе, поэтому решение, использующее предварительное вычисление для обеспечения эффективного запроса было бы предпочтительнее. Также обратите внимание, что требуется только минимальная сумма длин, а не фактические пути.
Любая помощь, идеи или предложения будут чрезвычайно оценены. Заранее большое спасибо!