Dijkstra的算法实现
我已经看到了dijkstra的加权图的算法，我应该怎么做才能在未加权图中找到最短路径？
我应该考虑所有边之间的权重0或1？
其次，我想在10^5节点上实现一个bfs来检查一个节点是否可以从任何其他节点到达？有没有可能，因为定义一个2-D数组的[10^5][10^5]给出了一个内存故障。
共有3个答案
使用0作为弧的代价将导致图中每个可能路径的代价相等，因此任何人都可能是最短的。
使用1意味着你所有的弧线都有相同的成本，所以Dijkstra会找到一条在你的开始和目标之间最小化弧线数量的路径。当然，可能会发生几个路径符合该条件，因此算法将返回其中一个。
我希望我的回答能有所帮助。
可以将未加权图视为每条边的权重为1。
对于大图上的BFS，请看一看大数据算法，这些算法使用“外部”内存（硬盘）存储完整的图，并对这些数据使用有效的数据访问技巧，以使算法工作的部分适合内存。有关开始信息，请参见：http://www.win.tue.nl/~hermanh/teaching/2IL35/AMM/04初等图算法。pdf
对于你的第一个问题，我确实在权重为1的未加权路径上实现了Dijkstra，它工作正常，但可能有更好的解决方案。
我不太记得bfs了，对不起！
-
本文向大家介绍Dijkstra的Java算法，包括了Dijkstra的Java算法的使用技巧和注意事项，需要的朋友参考一下 Dijkstra的算法是一种用于在加权图中的节点之间找到最短路径的算法。创建图形时，我们将使用新的addEdge和addDirectedEdge方法向边缘添加权重。让我们看看这个算法是如何工作的- 创建一个距离集合，并将除源节点以外的所有顶点距离设置为无穷大。 当距离为0时，
-
我们将用于确定最短路径的算法称为“Dijkstra算法”。Dijkstra算法是一种迭代算法，它为我们提供从一个特定起始节点到图中所有其他节点的最短路径。这也类似于广度优先搜索的结果。 为了跟踪从开始节点到每个目的地的总成本，我们将使用顶点类中的 dist 实例变量。 dist实例变量将包含从开始到所讨论的顶点的最小权重路径的当前总权重。该算法对图中的每个顶点重复一次;然而，我们在顶点上迭代的顺序
-
一、迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是
-
问题内容： 我正在尝试编写Dijkstra的算法，但是我在努力如何在代码中“说”某些事情而苦苦挣扎。为了可视化，这是我要使用数组表示的列： 因此，将有几个数组，如下面的代码所示： 粗体部分是我要坚持的地方-我正在尝试实现算法的这一部分： 3.对于当前节点，请考虑其所有未访问的邻居并计算其暂定距离。 例如，如果当前节点（A）的距离为6，并且将其与另一个节点（B）相连的边为2，则通过A到B的距离将为6
-
我试图使用邻接列表和PQ作为最小堆来实现单目标最短路径的Dijkstra算法。输出必须显示所有顶点到目标顶点的路径，如果路径存在，如果是，它的总和（最短），如果否，否路径。链接到整个代码 输入格式： 第一行是顶点数，n 第二行开始：（从1到n的顶点） 第一列是顶点 之后，多对， 根据GDB，它显示了在提取最小函数时发现的分段故障。 客户. c 从文本中提取输入。txt文件并创建一个有向图 服务器.
-
据我所知，dijkstra无法处理负边权重。为此，我们必须使用贝尔曼福特。 Bellman fords在负边权重和负循环下运行良好，这是无法从源位置访问到的，否则，它将返回消息“负循环存在”。 但是，上面显示的图表与dijkstra运行良好，即使存在负边权重。那么，如何知道何时使用具有负边权重的dijkstra？？ 我们想的是，dijkstra可以或不能使用负权重边。如果存在负循环，那么它将不起作