time - 在应用 Dijkstra 算法之前根据需要修剪图形是否值得？

Question

我在程序中使用 Dijkstra 算法。假设我有一个带有顶点和边的图。如果我们想象从源顶点“a”开始的所有边如下所示

a-->b        
a-->c   and  
a-->d  

并且所有以顶点“f”结尾的边是：

b-->f
m-->f
e-->f
w-->f

我从一开始就需要知道的是，我希望边缘a-->b作为我的起始边缘（假设“a”作为起点）所以不需要搜索“a”的其他邻居，即(a-->c and a-->d)

此外，我只想要以m-->f结尾的路径（假设“f”为目的地），即我不希望路径包含b-->f,m-->f,e-->f,w-->f

那么修剪我的初始图是不是一个好主意，因为它不包含这些边，然后在上面应用 Dijkstra？

实际上找到这些边缘需要一些搜索。我想知道是否值得（考虑时间或 CPU 使用率）进行搜索和修剪我的图表，还是有更好的方法？

Answer 1

为什么不只搜索从那时起的路径并b在m那之后添加你想要的边缘呢？如果你真的需要它，你可以添加一个特殊情况来排除包含边缘a并且f永远不会被添加到堆栈中 - 你必须检查这是否使它整体更快，我敢打赌它会在小图上但不是在非常大的（无论如何它只会以恒定的因素改变速度）。