onsider 五个顶点的图形，其顶点标记为 1 到 5。图形中存在的唯一边是从 1 到 2、1 到 3、1 到 4 和 1 到 5 各一条。让从 1 到 2、3、4 和 5 的旅行时间分别为 5、5、1 和 1 个单位。还假设如果从顶点 a 到 b 需要时间 t，那么从 b 到 a 需要相同的时间。我们希望选择从顶点 1 到其他顶点的步行，回到顶点 1，依此类推，直到每个顶点(顶点 1 除外 - 源(被恰好访问一次。
设初始时刻为 t = 0。设顶点 2、3、4 和 5 从 t = 0 的访问时间为 t2、t3、t4 和 t5。我们希望最小化 t2、t3、t4 和 t5 的总和。
找出给定时间的最小可能总和。
我无法理解问题本身
这是我对这个问题的理解：
如果按该顺序访问节点 2、3、4 和 5，则时间将为：
t2 = 5 (going from 1 to 2),
t3 = 15 (5 to get to 2, 5 to return from 2 back to 1, and 5 to go from 1 to 3),
t4 = 21 (15 + 5 + 1),
t5 = 23 (21 + 1 + 1).
总和为64。您可以使用不同的顺序获得更好的时间，您的任务是找到最佳(最小(总和。
为了尽量减少访问的总时间，我们首先选择花费最少时间的路径，因为这个时间堆积在所有其他顶点上。回到 1 后，我们选择具有第二个最短时间的路径，每次回到 1 后重复此过程。
让顶点 v1、v2、v3 和 v4 的时间按排序顺序为 a、b、c 和 d。然后在时间 t = a.我们在 t = 2a 时回到 1。然后我们在t = 2a + b处到达第二个顶点，并在t = 2a + 2b处回到1。继续类似地，顶点 v3 在 t = 2a + 2b + c 处访问，v4 在 t = 2a + 2b + 2c + d 处访问。因此，总和的最小值为 7a + 5b + 3c + d。
所以，答案是32。
so can we start the walk with vertex 5 =1+1=2
vertex 4 = 1+1=2
vertex 3=5+5=10
vertex 2= 5
total=2+2+10+5=19
请注意，无论您访问节点的顺序如何，您的总数都不会改变，因此您无法将其最小化。您可能希望与老师澄清这一点，但问题定义是"时间实例"，而不是持续时间。
把它想象成在时间 t-1 启动一个计时器 然后，对于上面的路径 (t-1 = 0(：t-5(vertex-5( = 1，t-4 = 3，t-2 = 9，t-3 = 19。总和为 32。比 64 好得多，所以你走在正确的轨道上！
Dijkstra 用于查找节点之间的最短路径，它不适用于此处。这个问题要容易得多。