寻找从所有节点到一个节点的最短路径的有效算法？
寻找从所有节点到一个节点的最短路径的有效算法有多种，其中最著名的算法是Dijkstra算法和Bellman-Ford算法。
- Dijkstra算法：
- 概念：Dijkstra算法是一种用于解决单源最短路径问题的贪心算法。它通过不断选择当前距离源节点最近的节点，并更新其他节点的距离值，最终得到从源节点到所有其他节点的最短路径。
- 分类：Dijkstra算法属于单源最短路径算法。
- 优势：Dijkstra算法能够高效地找到从源节点到其他节点的最短路径，并且适用于有向图和无向图。
- 应用场景：Dijkstra算法常用于路由选择、网络优化、地图导航等领域。
- 推荐的腾讯云相关产品：腾讯云提供了弹性MapReduce（EMR）服务，可以用于大规模数据处理和分析，其中包含了图计算框架GraphX，可以用于实现Dijkstra算法。
- 产品介绍链接地址：腾讯云弹性MapReduce（EMR）
- Bellman-Ford算法：
- 概念：Bellman-Ford算法是一种用于解决单源最短路径问题的动态规划算法。它通过对所有边进行松弛操作，不断更新节点的距离值，直到达到最优解。
- 分类：Bellman-Ford算法属于单源最短路径算法。
- 优势：Bellman-Ford算法能够处理带有负权边的图，并且可以检测负权环。
- 应用场景：Bellman-Ford算法常用于网络路由、链路状态协议等领域。
- 推荐的腾讯云相关产品：腾讯云提供了弹性容器实例（Elastic Container Instance，ECI）服务，可以用于快速部署容器化应用，其中包含了Kubernetes集群管理工具，可以用于实现Bellman-Ford算法。
- 产品介绍链接地址：腾讯云弹性容器实例（ECI）
以上是关于寻找从所有节点到一个节点的最短路径的有效算法的介绍。请注意，这只是其中的两种算法，还有其他算法如Floyd-Warshall算法、A*算法等也可以用于解决最短路径问题。
相关·内容
我目前正在研究非负边权图中的最短路径问题。
我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。
直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
给了我一个图，包括一个起始点，其他顶点，边代表从一个顶点到另一个顶点的代价。我需要找到从起始顶点到目的地点的集合。预算是一定数额的美元，旅费总额应在预算范围内。如何实现Dijkstra的算法来解决这个问题？我认为我们通常使用Dijkstra来寻找两个固定顶点之间的最短路径。但我不知道如何在这个预算问题上执行Dijkstra。如果有人能给出一些想法，那真的很有帮助！
浏览 6提问于2017-11-15得票数 2
回答已采纳
2回答
像Bellman算法和Dijkstra算法这样的算法存在于寻找从图上的单个起始顶点到每个其他顶点的最短路径。然而，在我编写的程序中，起始顶点的变化要比目标顶点更频繁。有什么算法做相反的--也就是，给定一个目标顶点，从每个起始点找到最短路径？
浏览 3提问于2015-02-27得票数 5
回答已采纳
有人告诉我，BFS可以为您提供从源顶点到目标顶点的最短路径，这是有意义的，因为您遍历相邻节点。然而，我看不到如何保证总是会发生这种情况。在BFS伪代码逻辑中，我看不到选择正确的相邻节点来保证具有最短路径。BFS可以随机选取任何相邻节点，最终得到从源顶点到目标顶点的更长路径。那么BFS如何给出从源顶点到目标顶点的最短路径呢？
浏览 1提问于2020-11-30得票数 1
1回答
用堆栈求加权图的最短路径
、、、
我会得到一些这样的图表，如下图所示。我已经搜索了一些算法，但它的接缝似乎是一些不可能的事情，对我来说，它们是不可能的。事实上，使用是可能的，但不幸的是，我只能使用堆栈(而不是矩阵)。我也寻找，但我无法得到与我的问题的关系。
显然，我的目标是从一个点到另一个点得到所有最短路径。正如我前面提到的，我将用向量字符串从我的堆栈输出解决方案。我想我必须访问每个节点，而我最害怕的是在搜索过程中被堆叠成一个循环，甚至失去跟踪。还请注意，这是，而不是有向图。如果Dijkstra的算法适用于这里，我将非常感谢你们中的任何人来指导我，我非常感谢任何帮助、建议、想法，甚至是在搜索过程中不要被堆叠在一起或松开轨
浏览 0提问于2013-11-15得票数 2
回答已采纳
3回答
我发现了许多关于寻找最短路径或问题的最佳/最佳解决方案的算法和方法。然而，我想要做的是一个算法，它能找到从一个点到另一个点的前K-最短路径。我面临的问题更像是在树中搜索，在每一步中都有多个选项，每个选项都有其权重。面对这类问题，使用了什么样的算法？
浏览 3提问于2010-11-19得票数 1
2回答
我使用netwrokx计算不同顶点之间的最短路径，使用Dijkstra算法。我有一个例子，我想连接三个不同的顶点(例如，A，B和C在一个无向图中)。首先，我找到了从A到B的最短路径，然后我想要找到从A到B的路径的最短路径。到目前为止，我尝试的是从A到B路径的所有节点到C的最短路径长度，然后计算出从节点到给定最小路径长度的最短路径。这是计算密集型的，因为路径可能有多达200到300个节点。
有人能给我一个提示吗?我如何改进方法？或者更容易找到从已有的边缘到目标的最短路径？
浏览 1提问于2018-08-15得票数 2
回答已采纳
2回答
我想知道是否有一种算法可以在图中找到最短路径。
假设我有一个图，从一个顶点到另一个顶点有一对路径。这些路径中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法会找到最短路径，但他们只“选择”一条。
浏览 1提问于2010-08-09得票数 1
回答已采纳
1回答
如何在图或ANN中引导信息流？
、、、、
我正在构建一个无方向的ANN。没有不同的输入或输出节点，并且所有连接都是无定向的。
为了使网络工作，我正在设计系统，将每个节点的动作阈值和加权关系视为其到“焦点”节点(临时输出节点)的距离的函数。
换句话说，我将任意选择一个或一组节点作为数据的端点和输出。此节点可以随时更改。流经图形的信息流将像磁铁一样吸引所选节点，因为从统计上讲，靠近末端节点的节点更有可能激活并沿该路径发送信息。
我希望这可以创建一个非常动态和现实的ANN模式，具有非常准确的学习模式。
现在，我被困在如何有效地确定每个节点到末端节点的距离的问题上。据我所知，如果我使用Neo4j，平均需要大约250ms来计算两点之间的最短路径
浏览 0提问于2011-07-30得票数 2
回答已采纳
4回答
给定一个有向图G=(V,E)，两个顶点s，t和两个权重函数w1，w2，我需要在<代码>D10</代码>从s到t的所有最短路径中找到w2到s的最短路径。首先，如何找到两个顶点s和t之间的所有最短路径？Dijkstra的算法帮助我们找到从一个顶点到每个其他可访问顶点的最短路径，是否可以修改它以获得两个顶点之间的所有最短路径？
浏览 0提问于2013-05-11得票数 4
我最近正在学习图形算法，在我的大学里，我们被教导说，Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对最短路径)。然而，我不明白这个算法是如何实现的，我试图通过观看YouTube视频和查找维基百科中的定义来理解它……
现在问题来了：
我无法找到描述该算法的资源，其结果将是所有对最短路径表，但只能“从一个节点到所有其他节点”。
对Bellman算法进行调整以实现所有对最短路径表，还是我的大学讲师在这方面完全错了？(他解释了一些提供所有对最短路径的算法，他称之为Bellman，但我认为这不可能是Bellman)。
编辑:我绝对理解Bellman算法中的“从一个节点到所有其他节点的最
浏览 8提问于2017-07-16得票数 1
回答已采纳
网络节点=住宅单位、医院
网络边=权重等于长度的道路
如何计算每个住宅大厦到附近任何医院的最短距离？
我使用"nx.all_pairs_dijkstra_path_length“，然后过滤出每个住宅节点到医院节点的最短路径。有没有更快更好的方法？
浏览 0提问于2018-07-02得票数 1
回答已采纳
2回答
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
3回答
Dijkstra算法能否找到从一个源顶点到所有其他顶点的所有最短路径，使得该路径访问一个无向对称图中的所有顶点一次且恰好一次？对称图有没有更快的算法？
浏览 1提问于2013-06-07得票数 4
回答已采纳
1回答
图中每个顶点之间的距离
、、、
是否有一种计算图中每个顶点到所有其他顶点的距离的近似/有效方法。
与Dijkstra不同的是，我正在寻找一种方法来计算所有顶点到所有顶点的距离(不是一个对所有顶点)。
谢谢!
浏览 7提问于2015-02-01得票数 4
回答已采纳
在图形上，有多个起点和终点。每个起点对应于多个终点，而每个终点仅对应于一个起点。我需要在地图上找到从起点到终点的所有路线。不同的路线不能交叉，但允许它们重叠。
在开始时，我使用A*算法来寻找每一条路由，但后一条路由采用了更多的路径，以避免与前一条路由交叉。我想知道是否有一个算法可以考虑所有路由的总长度。
浏览 35提问于2021-10-23得票数 0
我感兴趣的是寻找从网络中的所有点到特定点的最短路径。到目前为止，我一直在通过循环遍历所有点来计算最短路径来估计这一点。 随着网络规模的增加，这种方法的计算代价很高。有没有有效的替代方案？在NetworkX中有什么我忽略的地方吗？ # Pseudocode
For a_node in list_of_nodes:
shortest_path_to_poi = nx.shortest_path(G, source=a_node, target=poi, method='dijkstra') 感谢您的时间和调理。
浏览 51提问于2020-07-04得票数 0
回答已采纳
如何找到节点在无向图中，从该节点到所有其他节点的最小距离之和是最小的。我已经用dfs遍历了这个图。
我已经找到了到源节点的最小距离。策略是什么？
我的尝试-
import java.util.LinkedList;
import java.util.Scanner;
class Edge {
int from;
int to;
long wt;
Edge(int a, int b, long w)
{
from = a;
to = b;
wt = w;
}
}
class Graph {
浏览 1提问于2020-06-05得票数 0
1回答
在询问了一些关于最短路径算法()的一般性建议，然后询问了更具体的实现()之后，我决定使用JUNG库()。
我现在的目标是从A点到B点的最短路径，方法是使用点列表中的任意组合点(大小~1000)，其中每个点直接连接到x距离内的所有点。
为此，我需要建立一个树图。我相信这是树映射实现的列表：
对吗？现在，所有这些实现都局限于稀疏树映射，但是我必须创建一个相当密集的树映射。
那么，我应该用什么树图来完成我的目标呢？
浏览 0提问于2011-03-09得票数 2
回答已采纳
2回答
我正在寻找一种算法，我肯定已经研究过了，但我对图论还不太熟悉，甚至不知道要搜索的正确术语。
在抽象中，我正在寻找一种算法来确定可达顶点x1、x2、xn和某个起始点之间的路由集，当每条边都有一个权重，而每条路径只能有给定的最大总重量x时。
从更实际的角度来说，我有公路网，每个路段都有一个长度和最大的旅行速度。我需要确定从网络上的任何起点到某一时间范围内可以到达的区域。如果我能找到在这段时间内可以到达的最远点，那么我将使用凸包算法来确定区域(这对我的用例来说已经足够了)。
那么，我的问题是，我如何找到这些终点？我的第一个直觉是使用Dijkstra的算法，并在我“消耗”了一定的“预算”时间后停止，从
浏览 3提问于2015-07-09得票数 3
回答已采纳
是否有可能使用从Graphs.jl模块获取从源顶点到目标顶点的整个路径？
有一个update_vertex！(访问者，u，v，d)在更新顶点距离时调用的方法。距离是否仅在找到属于最短路径的新顶点时才更新？我不太确定。
谢谢。
编辑：
根据文档，可以使用与、dists、和连接来重建最短路径，但我不确定如何实现。我想在我的GenericGraph.上运行它
知道吗？
浏览 0提问于2016-03-31得票数 2
回答已采纳
1回答
停止路径处理
、、、
我是neo4j的新手，并试图了解如何优化路由查询。
我和OSM db一起工作。
我试图计算出从一个点到另一个点的距离。
START a=node(760119)
MATCH path=(a)-[:NEXT|NODE*1..30]-(c)
WHERE HAS(c.node_osm_id) AND c.node_osm_id=283103898
RETURN DISTINCT reduce(
distance = 0, n in filter(
x in path where has(x.length)
) | distance + n.length
) A
浏览 3提问于2013-11-22得票数 0
回答已采纳
1回答
下面是我所遵循的教程的链接：
以下是代码：
void BFS(vector<int> adj[], int N, int src)
{
int dist[N];
for(int i = 0;i<N;i++) dist[i] = INT_MAX;
queue<int> q;
dist[src] = 0;
q.push(src);
while(q.empty()==false)
{
int node = q.front();
q.pop();
浏览 2提问于2021-07-18得票数 1
在我的未加权图中，我需要从一个源顶点到达一个施加的顶点，然后返回到源。所有顶点最多只能访问一次。(该图中可能存在循环。)我想知道这样的最短路径的长度。
寻找“快速”算法：
我已经用Python做了几次尝试，但速度还不够快。;-)最新示例:生成器生成从源到附加点的所有路径(按长度递增的顺序)，每次我获得新路径时，将其与所有已计算的路径进行比较，如果不相交，则停止。效果很好，但太慢/内存太贵。早些时候(同样的问题)：考虑具有以下信息的子状态:位置、是否已到达施加点、已访问的顶点集……结果也不错，但速度太慢/内存太贵。
欢迎使用DP解决方案。
在谷歌上找不到任何东西。如果你知道哪里有什么，请告诉我。
浏览 1提问于2019-07-31得票数 0
基本最短路径问题和最短路径问题有什么区别？
一个最短路径问题，通过在图中找到从源节点到目标节点t的最短路径来解决。
一个简单的最短路径问题，通过在图中找到从源节点到目标节点t的最短路径，使得最短路径上的每个弧最多使用1次。
什么是基本的最短路径？
浏览 3提问于2020-03-19得票数 1
回答已采纳
2回答
考虑一个网格(X乘以Y)。网格中的每个点都有一个值Z。现在，在这个网格中有一个指定检查点的i号。假设网格有一个等级D。这个值D意味着您只需要穿过一个具有最大值D的路径就可以从任意一个检查点到另一个检查点。路径的长度由该路径中两个连续节点之间的最大海拔差决定。例如，考虑一个由高地组成的网格：
1 1 1 1 1
2 1 3 1 2
1 2 3 1 2
浏览 7提问于2014-01-13得票数 0
回答已采纳
2回答
给出了一个无向图，它具有普通边和特殊边，我们的目的是求出两个顶点(从顶点到顶点)之间的最短路径权值的和，其只遍历等于或少于一次<code>E 210</code>。换句话说，有多个特定的边，最多只能使用其中一个。
这是我在数据结构家庭作业中遇到的一个问题，我坚持了在图中存储边的权重的第一步。因为图中有两种边，所以我不知道如何解决这个问题。
我知道使用Dijkstra算法可以获得最短路径，但在此过程中，如何修改算法以满足限制的要求？
非常感谢你回答我的问题！
浏览 1提问于2021-12-06得票数 1
回答已采纳
4回答
所有对最短路径问题的最快实现？
、、、、
我有一个加权图30k节点160k边，没有负权重。我想计算从所有节点到其他节点的所有最短路径。我想我不能假设任何特定的启发式方法来简化问题。
我尝试使用这个Dijkstra C实现，即针对单个最短路径问题，对我的所有30个节点调用函数dijkstras()。正如您可以想象的那样，这需要很长时间。目前我没有时间自己编写和调试代码，我必须尽快计算这些路径，并将它们存储在数据库中，所以我正在寻找另一个更快的解决方案来准备使用，你有什么建议吗？
我不得不在最近的一台8 8GB内存的macbook pro上运行它，我想找到一个不超过24小时就能完成计算的解决方案。
提前谢谢你！
尤金尼奥
浏览 0提问于2011-08-24得票数 7
2回答
我不确定我在这里是否使用了正确的术语。我试图想出一个算法，让我们在任意图中找到一个顶点，这样顶点与最远顶点的距离最小。
另外，我还想出一个算法，让我找到两个顶点，而不是一个，再把最远的顶点到这两个顶点之间的距离最小化。
我的直觉说，我应该想出一个算法，计算出图中所有顶点之间的最短路径，然后查看路径，找到流量最高的顶点。但是我很难想出一个具体的算法，因为我以前根本没有这方面的经验。我试着用谷歌搜索这个问题，但没有成功。如有任何指导，将不胜感激。
浏览 0提问于2016-11-01得票数 -2
回答已采纳
2回答
给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。
我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra的算法？
我现在很挣扎。任何帮助都将不胜感激！
浏览 4提问于2014-02-04得票数 0
回答已采纳
1回答
使用限制提升c++ Astar
、、、、
我使用的是boost 的astar算法
我想为从起始节点到目标节点的路径长度积分一个长度条件。更具体地说，我试图找到一个精确长度为11位的数字链。一个想法可能是集成到boost A*实现的访问者模式中。但到目前为止，我还没有找到好的解决方案。
更一般的是，我正在寻找一种方法，将语法检查集成到A*算法中。在我的具体例子中，语法可以用一个规则模式来表示，比如^1-9\d{10}$每个节点代表一个字符(这里是一个数字)。任何建议都是值得感谢的。
浏览 2提问于2017-12-27得票数 0
我有一个非常简单的寻路任务-一个在8x8网格上玩的棋盘游戏，每个方块要么可以通过，要么不能通过。我正在寻找的是一个算法，它将给我从某个正方形A到正方形B的最佳n条路径(假设有)。
我一直在寻找A*，但据我所知，没有明确的方法来扩展它以找到多个路径。
所以，关键是它给出的路径实际上是最短的n条路径，它不会遗漏任何路径。效率也非常重要。有没有人能建议一个合适的算法，或者给我指明正确的方向？
浏览 0提问于2011-06-05得票数 3
1回答
我有一个带有未加权边的无向连通图。如何构建生成树(解决方案可能不是唯一的)，以便最小化所有节点的深度总和？这显然不是寻找最小生成树，因为边的“权重”实际上取决于孩子的深度。
我认为，给定一个指定的根，深度和最小的树可以通过贪婪地将所有可以连接的子节点以广度优先的顺序连接到每个节点来形成。因此，我将通过应用相同的程序N次，指定N个节点中的每个节点作为根，并从N个候选节点中选择最小的一个，来找到总深度最小的树。这是一个有效的算法吗？如果它是错误的，或者是否存在更有效的方法，请指出。
浏览 8提问于2013-02-22得票数 8
回答已采纳
我有一个简单的图表，我需要找到这个图表的启发式成本。
图是(矩阵表示)：
0 1 2 0 0 0 0
1 0 0 3 3 2 0
3 0 0 2 0 0 0
0 3 1 0 1 0 0
0 3 0 1 0 6 0
0 2 0 0 6 0 2
0 0 0 0 0 2 0
图片：
括号中的值表示当前目标顶点的顶点的启发式成本。
绿色顶点是开始，红色顶点是目标。
我创建了这个遗传成本矩阵：
0 2 6 3 1 9 5
9 0 2 4 6 4 1
1 3 0 5 2 9 4
3 1 5 0 1 7 8
0 6 2 1 0 10 14
2 1 6 3 7 0 5
1 4 3 2 1 3 0
我
浏览 0提问于2014-05-04得票数 0
1回答
我实现了一个名为dijkstra()的函数，它返回从原点到目的地的最短路径。我想添加一个修改，以便路径通过特定的节点。其结果是：
def checkpoint(G, origin, destination, extra):
path1 = dijkstra(G,origin,extra)['path'] # returns a list with the path
path2 = dijkstra(G,extra,destination)['path']
path = path1 + path2
retur
浏览 2提问于2021-10-08得票数 0
回答已采纳
我需要一些帮助在Mysql和Php中实现最短路径问题。据我所知，BFS算法是在无向图和无权图中找到这些路径的最佳方法。不过，我必须得到从一个顶点到另一个顶点的所有最短路径，这就变得更复杂了。我已经找到了一个Java实现，但它太复杂了，我无法将其转换为Sql。
所以，第一个问题是:我应该在哪里进行计算？Mysql还是Php？哪里会更快？
而且，BFS是最好的选择吗？是否有更容易实现的解决方案？如果没有，是否有人可以很容易地使用我的代码作为参考呢？
谢谢!
浏览 3提问于2015-11-06得票数 1
给定一个有向加权图(没有负边)，从一个节点到另一个节点的最短距离是多少，并且满足从一个节点/顶点到另一个节点/顶点的“跳数”必须小于某个特定值k的条件。(其中k肯定小于节点的数量)。
一个“跳”被定义为从一个节点移动到另一个节点，并且“跳”值从源节点从1开始。
这个问题并不像简单地运行Dijkstra算法那么简单，因为这个算法只给出了最短的距离，而没有考虑“跳数”。
考虑1:从源节点到端节点的最短路径可能超过允许的最大跳数。
考虑2:增加Dijkstra算法以最小化“跳数”将给你一个可能的答案，但它可能不是最短的。
请注意，这里的优先事项仍然是最小化最短距离，只是有了一个新的条件，即“跳数”需
浏览 2提问于2019-03-29得票数 1
1回答
像Bellman算法和Dijkstra算法这样的算法存在于寻找从图上的单个起始顶点到每个其他顶点的最短路径。它们的多源版本可以通过反转所有边缘并将目标作为开始节点来实现。
我想把它扩展到寻找图上源的“重心”(即“最接近”一组源的顶点)，找到“公平”的“一致”顶点路径。
是否已经有算法提供了这一点？他们是什么?
浏览 2提问于2016-11-26得票数 2
回答已采纳
我使用的是Java，我想检查一个节点是否可以从另一个节点到达。图工厂算法似乎不包含类似的内容。
提前感谢
阿尔托伯
浏览 4提问于2014-01-14得票数 1
回答已采纳
1回答
问题是如何从起始顶点到directed graph中的所有其他顶点寻找最短路径。
但是图有m positive加权边和k negative加权边，并且保证了负加权边不会在一个循环中。换句话说，在这个图中没有负的加权循环。
我试图直接使用Bellman-Ford和SPFA来解决这个问题，但是有没有更快的方法来解决这个问题呢？
浏览 4提问于2020-12-16得票数 3
回答已采纳
1回答
我的理解是，BFS和DFS是图遍历算法，而其他算法(如A*和dijkstra )则用于在图的两个节点之间寻找最短路径。但是在一些地方，我认为BFS和DFS也被称为最短路径查找算法。请详细说明图遍历算法与最短路径查找算法的区别。谢谢!
浏览 6提问于2022-05-06得票数 0
1回答
网络x图与弗洛伊德战争
、、、、
我是Python的新手。我有一个类似于这个的映射，我希望使用网络x创建从每个节点到每个其他节点的最短路径。
shp = nx.read_shp("../Shapefiles/Shapefiles/Station_in_Corridors/Group_1.shp")
G = nx.DiGraph()
for data in shp.edges(data = True):
G.add_edge(data[0],data[1],weight = data[2]["Length_Km"])
nx.floyd_warshall(G)
pos = nx.sprin
浏览 2提问于2018-11-23得票数 0
1回答
对于Boost库和c++语言，我都是新手。
我已经使用Boost创建了一个图，并添加了顶点和边，并在graphviz中输出了该图。
现在，我想执行从一个顶点到图中所有其他顶点的广度优先和深度优先搜索。
结果应该是从起始顶点到图中其他顶点的最短路径。
我如何在Boost中实现这一点？任何帮助都将不胜感激。
提前感谢你了。
我还添加了我的源代码供您参考。
#include "stdafx.h"
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/g
浏览 0提问于2012-09-03得票数 1
我正在设计一个系统，以找到最短的路径覆盖最少的细胞。假设平面被分成矩形单元。什么才是最适合的算法。我只是在寻找先头，而不是适当的代码或实现。
浏览 3提问于2015-06-29得票数 0
回答已采纳
4回答
二维网格(x，y)上有N个点。我需要找到最短的路径，从点A到点B，但我只能从一个点到另一个点，如果两点之间的距离大于距离D，我就不能在两点之间旅行。我认为可以通过使用某种修改的Dijkstra算法来解决这个问题，但我不确定如何解决，因为我以前从未实现过它，只是在Wiki上研究了它。
浏览 0提问于2014-02-08得票数 0
3回答
我正在尝试实现Dijkstra的算法，它可以找到起始节点和结束节点之间的最短路径。在到达终端节点之前，有一些必须通过的中间节点(多个)，例如，两个或三个必须通过节点，这些节点必须在到达端节点之前经过。
如果我有一个必须传递节点，我找到的解决方案是找到两个不同的路径，从必须传递节点到目的地，从必须传递节点到启动节点。
我想不出如何实现这样的算法。有什么建议吗？
谢谢。
List<Node> closestPathFromOrigin = null;
double maxD = Double.POSITIVE_INFINITY;
double _distance = 0;
int t
浏览 3提问于2014-08-18得票数 3
回答已采纳
1回答
我最近不得不看看Dijkstra算法，它证明了这一点。
算法的证明在我能找到的所有来源中终止，所有顶点的数量和访问的所有顶点的数量相等(例如R=V或S=V)。此外，当Q(作为图的所有顶点初始化)为空时，该算法的while循环终止，因此必须访问所有顶点。
我不明白为什么一定要这样。有没有这样的图，算法不必访问所有的顶点，例如:起始顶点直接连接到权重为1的“查找”顶点，并连接到权重为10的其他顶点。
我希望你能理解我在这里遇到的问题。
编辑:这是我在科尔曼使用的伪代码：
浏览 2提问于2018-06-08得票数 2
给出：有向图G(V，E)和s,t是V的顶点，除边(u,v)为负外，所有边均为正。
问题：找到从s到t的最短路径(的意思是:具有最小的权重)。
我的解决方案：，因为我们有一个负的边缘，所以我们应该使用Bellman的算法。在边缘执行n-1 "relax“，如果在n的第四次迭代中出现问题，就会有一个循环--从而返回false.。否则，返回从s到t的最短路径。
另一种解决方案：使用Dijkstra，通过保存d(u)和传递负边(u，v)并进行“放松”来稍微改变它，然后我们再次在没有负边的所有边上，如果改变了距离，我们就会有一个循环，否则就会返回最短的路径。
注：我显然不确定我的解决方案，有一个
浏览 2提问于2017-06-03得票数 1
回答已采纳
1回答
我有一个关于BFS的问题。在展开节点后，无论是图还是树，BFS将采用什么路径作为从起点到目标的解决方案？它是否考虑了从一个节点移动到另一个节点的成本，并采用最低成本的路由，还是采用到达目标所需节点数量最少的路径？
浏览 23提问于2021-04-13得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
