问题如下：
您有n个domino片段和每个domino片段上的两个数字（n个片段），还有一个额外的m个domino片段集，但是您只能使用这个集合中的一个片段（最多）来帮助您执行以下操作：
计算可用于从给定起点s到终点d的最小domino块数。
意思是开始部分应该有数字，结束部分应该有数字。
输入：
和多米诺骨牌的数字（n对）。
m和额外的多米诺骨牌碎片数（m对）。
起点S和终点D。
输出：
多米诺骨牌的最小数量。
我正在考虑使用bfs来解决这个问题，我可以从s开始，通过不断地从图中删除节点m（i）并添加节点m（i+1），找到到d的最小路径。
但是这样做的时间复杂度将是O（n*m）。
但不仅如此，可以有多个起始点S，所以复杂性将是O（s s *n*m）。
能用更好的方法解决吗？
老师说它可以在线性时间内解决，但我只是很困惑。
最佳答案
我最初错过了你的问题允许多个来源，并写了一个有点长的答案解释如何处理这个问题。不管怎样，我还是把它贴在这里吧，因为它可能还是有帮助的。进一步滚动以获取原始问题的解决方案。
线性时间内求单s到d的最短路径
让我们逐步建立这个想法。首先，让我们尝试解决这个问题的一个更简单的版本，在这个版本中，我们只需要找出是否可以通过使用额外的m多米诺骨牌集中的至多一个多米诺骨牌，从单个s到单个d。
我建议这样做：在N个多米诺骨牌上做一些预处理，让每个M多米诺骨牌快速地（在固定的时间内）回答是否存在一个从S到D的路径，通过这个Domino。（当然，当我们根本不需要额外的domino时，我们需要记住edge情况，但它很容易在线性时间内覆盖。）
什么样的信息能让你回答这个问题？假设您看到的是一个多米诺骨牌，其末端有数字a和B如果你知道你可以从S到A，从B到D，你用这个多米诺骨牌从S到D，对吧或者，如果有一条从S到B和从A到D的路径，它也会起作用。如果两者都不是真的，那么这个domino就无法帮助您从s到d。
这很好，但是如果我们从每个可能的B运行BFS，我们将无法实现线性时间复杂度。但是，请注意，您可以反转第二个问题（检测是否存在从B到D的路径），并将其设为“我能从D到每一个可能的B”吗？这很容易用一个朋友来回答。
你能看到这种方法是如何适应于找出每个Domino最短路径的长度，而不是仅仅检测路径是否存在。
线性时间内求多个S到D的最短路径
让我们把问题反过来说，我们想找到从d到多s的最短路径。你可以创建一个有向图，它的节点数是多米诺骨牌上唯一数字的两倍。也就是说，对于每个数字，都有节点V和V'，如果您在V中，则表示您还没有使用额外的domino，但如果您在V中，则表示您已经使用了一个domino每个核心（即，原始n个domino（a，b）中的一个）对应于图中的4条边：（a->b），（b->a），（a'->b'），（b'->a'）。每个额外的domino对应两条边：（A->B'），（B->A'）注意，一旦我们进入了一个节点，我们就永远无法离开它，所以这样最多只能使用一个额外的domino。图中D的一个BFS将回答这个问题。
关于algorithm - 这是我能得到的最好的复杂性吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56178422/