我们给出了未加权的无向图G =(V,E)其中| V | <= 40,000和| E | <= 10 6.我们还给出了四个顶点a,b,a',b'.有没有办法找到两个节点不相交的路径a - > a'和b - > b',使它们的长度之和最小？
我的第一个想法是首先找到最短路径a - > a',从图中删除它,然后找到最短路径b - > b'.我不认为这种贪婪的方法会起作用.
注意:在整个应用程序中,a和b是固定的,而'和b'在每个查询中都会发生变化,因此使用预计算以提供有效查询的解决方案将更为可取.另请注意,只需要最小长度总和,而不是实际路径.
任何帮助,想法或建议都将非常感激.非常感谢提前!