boost最短路径查找算法
你好，亲爱的朋友们。
我想在随机图中找到最短路径。我使用boost图形库。据我所知，我需要利用点之间的现有距离构建图形。之后，我需要使用一些算法。。。
正如我所见，Dijkstra的算法实际上是找到从1点到其他点的所有路径。（应该很慢？）
A*需要一些额外的数据（不仅仅是距离）
如何找到2点之间的最短路径？我在bgl文件夹中看到了许多最短路径算法标头，但我没有找到如何使用它们的示例。
此外，我可以预先计算一些图形是必要的。
我该怎么办？
共有2个答案
Dijkstra的算法需要O（E log（n））时间-其中E=#边，N=#节点。它应该足够快。请评论E和N的近似值。
在某些情况下（例如社交图），以下方法更快：-假设边权重为1，N非常大，节点程度很小（几百）：从node1执行2级BFS，从node2执行2级BFS并相交集合。如果路径长度为
这取决于你有多少个节点，正如你提到的，你的节点在O（10^4）左右，边是O（10^4），这很好
所以在BOOST LIBRARY DOCS中，它的时间复杂度是O（V log V E）。所以如果你把V=10^4和E=10^4放在一起，你会得到O（10^5），这很好，在普通计算机上可以运行不到1秒，所以你可以使用它。
A*算法可以比Dijkstra算法运行得更快，但它需要一个启发式函数，该函数必须是单调且可接受的，并且根据您的问题可能很难找到该函数。
所以我觉得Dijkstra对你的案子有帮助
-
主要内容：最短路径算法在给定的图存储结构中，从某一顶点到另一个顶点所经过的多条边称为 路径。 图 1 图存储结构 例如在图 1 所示的图结构中，从顶点 A 到 B 的路径有多条，包括 A-B、A-C-B 和 A-D-B。当我们给图中的每条边赋予相应的权值后，就可以从众多路径中找出总权值最小的一条，这条路径就称为 最短路径。 图 2 无向带权图 以图 2 为例，从顶点 A 到 B 的路径有 3 条，它们各自的总权值是：
-
本文向大家介绍Javascript中的最短路径算法，包括了Javascript中的最短路径算法的使用技巧和注意事项，需要的朋友参考一下 在图论中，最短路径问题是在图中的两个顶点（或节点）之间找到路径的问题，以使其构成边的权重之和最小。在这里，我们需要修改添加边缘并添加有向方法，以允许向边缘添加权重。 让我们看看如何添加它- 示例 现在，当在图上添加一条边时，如果我们不指定权重，则会为该边分配默认
-
我已经从Cormen的第三版参考“算法介绍”中找到的伪代码中实现了Dijkstra算法，用于单源最短路径问题。 我的实现是在python上使用链接列表在邻接列表表示中表示图形。这意味着节点列表是一个链接列表，每个节点都有一个链接列表来表示每个节点的边缘。此外，我没有实现或使用任何二进制堆或斐波那契堆作为算法所需的最小优先级队列，因此当过程需要提取与源距离最小的下一个节点时，我在节点链表内搜索O（V
-
我试图找到shrotest路径之间的节点和使用Dijkstra算法，但每次它给我错误的响应。 下面是我的代码- 根据计算，从节点到节点的最短路径是，但我得到
-
本文向大家介绍java实现Dijkstra最短路径算法，包括了java实现Dijkstra最短路径算法的使用技巧和注意事项，需要的朋友参考一下 任务描述：在一个无向图中，获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra一般的表述
-
本文向大家介绍python编写的最短路径算法，包括了python编写的最短路径算法的使用技巧和注意事项，需要的朋友参考一下 一心想学习算法，很少去真正静下心来去研究，前几天趁着周末去了解了最短路径的资料，用python写了一个最短路径算法。算法是基于带权无向图去寻找两个点之间的最短路径，数据存储用邻接矩阵记录。首先画出一幅无向图如下，标出各个节点之间的权值。 其中对应索引： A ——> 0 B——