如果我修改它，我可以在加权图上使用广度优先搜索吗？
Can I use Breadth-First-Search on weighted graphs if I modify it?
我正在与朋友讨论以下方法是否有效：
我们最近在一次关于广度优先搜索的讲座中学到了。我知道这是 Dijkstra 的一个特例，其中每个边缘权重都设置为一个。假设现在给定一个图，其中的边具有大于 1 的整数权重。然后我将通过引入额外的顶点并通过权重为 1 的边连接它们来修改此图，例如假设我们有一条权重为 3 的边连接顶点 u 和 v，那么我将引入虚拟顶点 d1、d2，删除连接 u 和 v 的边，而是添加边 {u, d1}, {d1, d2}, {重量一的 d2,v}。
如果我以这种方式修改我的整个图，然后从一个原始顶点开始应用广度优先搜索，这不是也有效吗？
非常感谢您！
由于 BFS 保证 return 未加权图上的最佳路径，并且您已经创建了原始图的未加权等价物，因此您将保证获得最短路径。
在 Dijkstra 算法上这样做失去的是运行时最优性。现在你的算法的运行时间取决于边的权重，而 Dijkstra 的只取决于边的数量。
这种思想实验是了解 Dijkstra 算法工作原理的好方法（例如，您将如何修改算法以不需要创建新图？或者不对边采取 100 步重量为 100？）。事实上，这可能就是 Dijkstra 最初发现算法的方式。
我正在与朋友讨论以下方法是否有效：
我们最近在一次关于广度优先搜索的讲座中学到了。我知道这是 Dijkstra 的一个特例，其中每个边缘权重都设置为一个。假设现在给定一个图，其中的边具有大于 1 的整数权重。然后我将通过引入额外的顶点并通过权重为 1 的边连接它们来修改此图，例如假设我们有一条权重为 3 的边连接顶点 u 和 v，那么我将引入虚拟顶点 d1、d2，删除连接 u 和 v 的边，而是添加边 {u, d1}, {d1, d2}, {重量一的 d2,v}。
如果我以这种方式修改我的整个图，然后从一个原始顶点开始应用广度优先搜索，这不是也有效吗？
非常感谢您！
由于 BFS 保证 return 未加权图上的最佳路径，并且您已经创建了原始图的未加权等价物，因此您将保证获得最短路径。
在 Dijkstra 算法上这样做失去的是运行时最优性。现在你的算法的运行时间取决于边的权重，而 Dijkstra 的只取决于边的数量。
这种思想实验是了解 Dijkstra 算法工作原理的好方法（例如，您将如何修改算法以不需要创建新图？或者不对边采取 100 步重量为 100？）。事实上，这可能就是 Dijkstra 最初发现算法的方式。