我有一个类似于下面的无向图，我需要实现一个图遍历算法。示例：
https://i.stack.imgur.com/4BVPz.png
其思想是，每个顶点都是一座城市，每个边缘都是一条道路
边的权重表示遍历指定边所需的时间
条件是：
- 每个边都在指定的时间窗口中打开以进行遍历：时间打开1、时间打开2、时间关闭1、时间关闭2-当前时间必须在这些间隔中才能遍历边
- 只能访问某些顶点。每个顶点必须在指定的时间窗口内至少访问一次："打开时间1"、"打开时间2"、"关闭时间1"one_answers"关闭时间2"-当前时间必须在这些间隔内，才能将顶点标记为已访问
- 起点始终为顶点0
对于我的示例，我有：
必须访问的顶点及其时间窗口(带-1的值不考虑在内)：
Vertex To1 Tc1 To2 Tc2
1 0 260 340 770
4 0 240 -1 -1
5 170 450 -1 -1
边在以下时间窗口中打开(不考虑带-1的值考虑)：
Edge To1 Tc1 To2 Tc2
0-1 0 770 -1 -1
0-4 0 210 230 770
0-5 0 260 -1 -1
1-2 0 160 230 770
1-5 40 770 -1 -1
2-4 80 500 -1 -1
3-4 60 770 -1 -1
3-5 0 770 -1 -1
因此，基本思想是从顶点0开始，找到最短的路线来遍历顶点1、4和5
例如，如果您完成了0-1，但不能使用1-5，则可以执行0-1-0-1-5。
我现在使用的一个可能的解决方案是：
从0开始。在最短的时间内找到要标记的最近顶点(我使用修改的Dijkstra算法)。这样做，直到我标记了所有需要的顶点
问题是我认为我没有找到所有的可能性，因为正如我所说你也可以像0-1-0-1-5组合一样四处移动，最终你可能会选择更短的路线。
为了使其更加清晰，我必须找到最短路径，以便从顶点0开始，以一个目标顶点结束，同时我至少访问了一次所有其他目标顶点，同时考虑到施加在边和目标顶点上的条件
例如：
一个可能的解决方案是0-4-3-5-1，总时间为60+50+60+50=220
从0开始，我也可以直接转到5，但如条件中所述，以便标记顶点5我的累计时间必须在170到450之间。此外，如果我以0-4领先，我就不能使用4-2的优势，因为它在80分开始，我的累计时间是60分。注意，我可以使用0-4-3，因为4-3在60时打开，而要进行0-4，需要等于60的时间。
首先，限制是我将使用最多20个顶点最大时约50个边缘
解决方案1:
0
1 4 50 2 5 0 2 3 0 1 3
我所做的是通过访问每个相邻的顶点来遍历图，构建类似于树的东西。当出现以下情况时，我停止扩展分支：
1。我有太多重复项，比如0 1 0 4 0 1 0-所以我停止了，因为我有一组重复的0值，即4
2。我找到一条包含所有要标记
3的顶点的道路。我发现一条路比另一条完整的路要长
4。我无法创建另一个节点，因为边缘已关闭
解决方案2:
应用@Boris Strandjev示例，但我有一些问题：
我必须在节点1、4和5的间隔内至少访问一次，允许但不标记间隔外的访问。对于一个顶点，我有{(<id1，id2id3id4>，时间)}，其中id1是当前顶点的边，id2-4表示1,4,5的布尔值，如果在指定的时间间隔内访问，时间-路径中的当前时间
Step1:
{<0, 000>, 0} I can visit - {<1, 100>, 60} - chosen first lowest val
- {<4, 010>, 60}
- {<5, 000>, 60}
Step2:
{<1, 100>, 60} - {<0, 100>, 120}
- {<2, 100>, 110} - chosen
- {<5, 100>, 110}
Step3:
{<2, 100>, 110} - {<1, 100>, 160} - if I choose 1 again I will have a just go into a loop
- {<4, 110>, 170}
Step4:
{<4, 110>, 170} - {<0, 110>, 230}
- {<2, 110>, 230}
- {<3, 110>, 220} - chosen
Step5:
{<3, 110>, 220} - {<4, 110>, 270} - again possible loop
- {<5, 111>, 280}
Step6:
{<5, 111>, 280} - I stop Path: 0-1-2-4-3-5 cost 280
编辑：
我最终使用了以上两种解决方案的组合。一切似乎都很顺利。
我没有看到对图中顶点或边的数量有严格的限制，所以如果我的解决方案不适用，请原谅。如果你需要任何改进，都要给予更严格的限制。
一种可能的解决方案是扩展节点的定义。不要只将城市视为图中的节点，而是添加更多的属性。保持边定义为隐式，在移动中生成传出边，这样可以节省内存。
请立即查看：
您将节点定义为三项内容的组合：-节点所指的城市。-访问时间-访问的目标节点的位图(这样您就可以判断是否已经访问了所有目标)。
现在边缘有点复杂了——它们将你从一个城市带到另一个城市，但每条边缘也会改变相邻节点的时间。同时，每一步都要不断更新目标节点位图。
这里有一个例子：
您从<city:=0, time:=0, bitmap:= (0 - true, 1...k - false)>开始
如果您通过边缘0-4，您会发现自己处于节点<city:=4, time:=60, bitmap:= ({0,4} - true, {1...k} / {4} - false)>
使用Dejkstra算法，继续以这种方式在节点之间移动，你会找到你的解决方案(当你扩展节点定义时，现在甚至会考虑环形交叉路口)。只要您发现自己所在的节点在其位图中设置了所有位，就可以找到解决方案。
在这种解决方案中使用的节点数量不太容易计算，但对于相对有限的节点数量和非常有限的目标城市数量，它应该可以工作(问题是生成的节点数量相对于目标城市是指数级的)。
编辑
下面是您要求的扩展示例：
想象一下你有这样一个输入(我用的是你的符号)：
Vertex To1 Tc1 To2 Tc2
1 0 40 80 120
2 40 80 -1 -1
3 0 400 -1 -1
4 30 80 120 190
Edge To1 Tc1 Weight
1-2 0 770 50
1-4 30 70 30
1-3 0 400 30
3-4 100 200 50
2-4 0 400 20
我将用以下形式表示顶点：<1,1100>的意思是：当前顶点为1，第二个：第一个和第二个顶点已在找到的路径中访问。到每个顶点的距离将是到达该顶点所需的最短时间。
正如您所知，在Dijkstra算法的过程中，您正在考虑扩充路径(即您找到的到达已到达顶点前面每个顶点的最佳路径)。我将注意到每个扩充路径如下：(<1,1100>, 400)意味着当前可以到达顶点<1,1100>的最佳时间是400。
从一组扩充路径{(<1, 1000>, 0)}和到所有顶点的距离infinity开始该算法。现在按照下面的步骤操作。
第一个顶点是用最佳扩充路径到达的。由此，可能的边是1-2和1-3(1-4在第0秒不可用。它们触发了另外两条增强路径：{(<2, 1100>, 50), (<3, 1010>, 30)}到<1, 1000>的距离变为0。
下一步考虑最佳扩充路径CCD_ 13。然而，传出边的邻居可以用于添加扩充路径：不能使用1-3，因为在时间60不能访问顶点1。由于时间间隔的原因也不能使用边缘3-4。因此，扩充路径现在是：{(<2, 1100>, 50)}。
下一步：(<2, 1100>, 50)和新的扩充路径：{(<1, 1100>, 100), (<4, 1101>, 70)}。
下一步：(<4, 1101>, 70)，但也不添加新路径：顶点2在时间90不能访问，3-4不能再使用。因此，扩充路径是CCD_ 21。
下一步：(<1, 1100>, 100)，将扩充路径更改为：{(<3, 1110>, 130)}。
下一步：(<3, 1110>, 130)，它将扩充路径更改为：{(<4, 1111>, 180)}。
下一步：(<4, 1111>, 180)，这是最后一步-我们处于访问所有目标顶点的状态。所以总结一下：你可以在180秒内访问限制中的所有顶点。
我希望这个例子能帮助你理解我的想法。您可能需要将所有注意事项写在纸上，以使sur-eI不属于扩充路径。