在应用 Dijkstra 算法之前根据需要修剪图形是否值得？
我在程序中使用 Dijkstra 算法。假设我有一个带有顶点和边的图。如果我们想象从源顶点 "a" 开始的所有边如下
a-->b
a-->c and
a-->d
，以顶点 "f" 结束的所有边是：
b-->f
m-->f
e-->f
w-->f
我从一开始就需要知道的就是，我希望边缘 a-->b 作为我的起始边缘（假设 "a" 作为起始点），因此不需要搜索其他邻居"a" 即 (a-->c 和 a-->d)
另外我只想要以 m--> 结尾的路径;f （假设 "f" 作为目的地）即我不希望路径包含 b-->f,m-->f,e-- >f,w-->f
那么，修剪我的初始图形使其不包含这些边，然后对其应用 Dijkstra 是个好主意吗？
实际上找到这些边缘需要一些搜索。我想知道是否值得（考虑时间或 CPU 使用情况）进行搜索和修剪我的图表，或者有更好的方法吗？
I am using Dijkstra algorithm in a program. Suppose I have a graph with vertices and edges. If we imagine all the edges starting from source vertex "a" are as below
a-->b
a-->c and
a-->d
and all the edges ending to vertex "f" are:
b-->f
m-->f
e-->f
w-->f
what I need to know from the beginning is that, I want the edge a-->b as my starting edge (assume "a" as start point) so do not need to search for the other neighbors of "a" i.e. (a-->c and a-->d)
Also I only want the paths which end to m-->f (assume "f" as the destination) i.e. I do not want the path containing b-->f,m-->f,e-->f,w-->f
So is it a good idea to trim my initial graph as such it doesn't contain these edges and then apply Dijkstra on that?
Actually finding these edges needs some searches. I wonder if it is worth (considering time or CPU usage) doing searches and trimming my graph or there is a better way?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
为什么不直接搜索从
b到m的路径，然后添加您想要的边呢？如果您确实需要它，您可以添加一个特殊情况来排除包含a和f的边被添加到堆栈中 - 您必须检查是否存在使其整体速度更快，我敢打赌，它会在小图上出现，但不会在真正巨大的图上出现（无论如何，它只会以恒定因子改变速度）。Why not just search for a path from
btomthen and add the edges you want after that? If you really need it, you may add a special case to exclude edges containingaandffrom ever being added to the stack -- you'd have to check if that makes it faster overall, my bet is that it will on small graphs but not on really huge ones (it only changes speed by a constant factor anyways).