我已经在这个问题上停留了两天，但仍然没有任何进展。基本上，问题如下：给定一个无向的简单加权和连通图，我们必须找到从给定源到给定目的地的最短步行路程，同时访问给定集合A中的至少一个顶点和集合B中的至少一个顶点，并加上以下约束：来自集合B的顶点应该总是在访问来自集合A的顶点之后出现。集A和B是不相交的，并且图中可能存在既不属于A也不属于B的顶点。只有一个源顶点和目标顶点。
我试图将最短路径分解成一个访问顶点的路径，即A从源头访问v，然后从v到B中的另一个w，然后从w到目的地。可以使用分别具有不同起始顶点的3个Dijkstra通道来完成。但是，我必须选择最小的v，这样会导致O（V E log（V））复杂度，其中V =顶点数，E =边数。由于问题提出了我的要求，即我仅使用O（1）Dijkstra运行，因此我非常困于如何在O（E * log（V））中执行此操作。谁能帮我吗？
编辑：我们无法构建新图或对其进行修改，因为有人建议构建水平图。我必须以某种方式修改Dijkstra例程以解决此问题。Graph. Blue vertices are the set A, purple ones set B. Home is 0 and Destination is 8例如，在此图（请参阅链接）中，最短步行距离应为：0-> 1-> 0-> 3-> 6-> 7-> 8，总费用= 6
对我来说，解决此类问题的最简单方法是将图形顶点划分为“级别”（例如建筑物中的故事），并可能在多个级别之间复制某些顶点。
在您的情况下，将有5个级别，级别1、3和5包含所有顶点，而级别2仅具有A顶点，级别4仅具有B。起始顶点位于级别1，结束顶点位于级别5。原始边缘在每个级别内以及相邻级别之间复制。
修改后的图形中的任何路径都将通过A顶点，然后再通过B顶点，因为任何路径都必须依次通过所有5个级别。
除了按要求的顺序排列强制对以外，这种安排并不关心是否存在任何顺序的附加A和B顶点（因此允许x-x-x-x-A-B-A-B-x-x-x）。如果需要排除这些顶点，请删除级别1和3的所有B顶点，以及级别3和5的所有A顶点。
作为@n。'代词'm。指出，我们可以通过图分层来解决这个问题。专门针对我的情况，只需添加一个新的源顶点并将该源顶点的边添加到属于原始图A的所有顶点的边。这些边的权重将与从原始源到原始图形中此顶点的最短路径相同。同样，您添加一个新的目标顶点，并将所有B个顶点的边添加到该新顶点，并且边缘的权重再次是从B顶点到原始图形中原始目标顶点的最短路径。现在，如果将Dijkstra从新源运行到新目的地，您会看到至少要访问一个A顶点，然后B顶点才最终在新目的地结束。这条路径的确是最短的路径。