在非加权图中找到最短路径

在大学关于图论的课程中，我们讨论寻找最短路径，因此Dijkstra的算法出现了，在这一点上，我应该提到图的边缘是加权的， > 0。然后教授问我们如何找到最短路径，如果边缘没有加权，我认为同样的算法会做，因为边缘具有“相同”的非负权重。但他建议BFS。这是真的？ Dijkstra不会工作正确吗？我不是在寻找BFS找到路径，但既然它是详尽的，我想也许它会更好地避免它。在非加权图中找到最短路径

来源

2014-10-09 Libathos

如果我没有错，如果所有边的权重长度相等，则Dijkstra的算法会减少到BFS。 – 2014-10-09 07:41:11

哦，我认为这可能是一个可能性不确定。谢谢 – Libathos 2014-10-09 07:42:17

Dijsktra对我来说工作得很好，即使是没有图的图也是如此。每个连接的重量只有1.

来源

2014-10-09 07:39:45 Jure

是的，那也是我的第一个预感 – Libathos 2014-10-09 07:41:13

在非加权图中找到最短路径

回答

相关问题