如果我对加权图进行修改，可以使用宽度优先搜索吗？
如果我对加权图进行修改，可以使用宽度优先搜索吗？
提问于 2021-12-09 14:47:52
我正在与一位朋友进行讨论，如果以下内容有效的话：
我们最近在一堂关于广度优先搜索的讲座中学到了。我知道这是Dijkstra的一个特例，其中每个边的权重都设置为1。假设现在给出一个图，其中边有一个以上的整数权值。然后，通过引入附加顶点并通过边与权1连接来修改这个图，例如假设我们有一个连接顶点u和v的权3边，然后引入虚顶点d1，d2，删除连接u和v的边，而添加权重1的边{u，d1}，{d1，d2}，{d2，v}。
如果我用这种方式修改我的整个图，然后应用宽度优先搜索，从一个原始的顶点开始，这不也是工作的吗？
非常感谢您提前！
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-12-09 16:41:08
由于BFS保证在未加权图上返回最优路径，并且您已经创建了与原始图相同的未加权等价，因此可以保证得到最短路径。
通过Dijkstra的算法执行这个操作，失去了，这就是运行时最优性。现在，算法运行时依赖于边缘权重，而Dijkstra只依赖于边数。
这种思维实验是了解Dijkstra算法工作原理的一个很好的方法。如何修改算法，使其不需要创建新的图形？或不采取100步的边缘与重量100?)。事实上，这可能就是Dijkstra最初发现该算法的原因。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/70291888
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号