Dijkstra算法实现

Question

我见过dijkstra关于加权图的算法，我应该怎么做才能在未加权图中找到最短路径？

我应该考虑所有边0或1之间的权重吗？

其次，我想在10^5节点上实现一个bfs，以检查一个节点是否可以从任何其他节点访问？是否有可能，因为定义一个二维[10^5][10^5]数组会产生内存错误.

Answer 1

对于您的第一个问题，我在权重为1的未加权路径上实现了Dijkstra，它工作得很好，但可能有更好的解决方案。

我不记得太多关于bfs的事了，对不起！

Answer 2

你可以把一个未加权的图想象成每条边都有一个1的权重。

对于大图上的BFS，请查看使用“外部”内存(硬盘)存储完整图的大数据算法，并使用有效的数据访问技巧，以便该算法工作的部分适合内存。首先请参阅：http://www.win.tue.nl/~hermanh/teaching/2IL35/AMM/04-elementary-graph-algorithms.pdf

Answer 3

使用0作为弧的代价将导致图中的每条可能的路径的代价相等，因此任何人都可以是最短的。

使用1意味着您所有的弧都有相同的成本，因此Dijkstra将找到从开始到目标之间的最小弧数的路径。当然，可能会有几条路径符合这种条件，所以算法会返回其中的一条。

我希望我的回答能帮上忙。