如何找到 2 个顶点之间的所有可能路径
How to Find All possible paths between 2 vertices
我正在调试遗留代码，其中道路网络已由 Boost Graph 表示。
A_Star 搜索没有给我两个特定点之间的最短路径，我知道 boost 不会错（直到我调试了我的代码一千次）。
要手动调试，我需要知道如何打印2 个顶点之间的所有可能路径。在我的输出中，每条路径都应由一系列边及其相应的权重表示。
我很重视您的帮助和评论
A* 基于启发式。如果遗留使用 A*，则意味着问题更复杂，然后只需找到最短路径即可。
要找到2个顶点之间的最短路径，有一些图算法，Dijkstra是最容易实现的（确保同时进行循环检查）。这些是确定性的。
如果您需要知道 2 个顶点之间的所有路径，这个是 NP 完全路径，这意味着您需要进行回溯。
A*一般用来解决NP完全问题。结果不是最好的路径，只是在适当的时间内找到的一条非常好的路径。
A* 的启发式算法用于放弃递归或将算法从回溯法转换为广度优先搜索法（通常是后者）。
A* 算法和 Dijkstra 算法可解决的问题之间的差异示例如下（来自我的头脑）：
在曼哈顿找到从 X、Y 角到 X1、Y1 角的最短路线（可由 Dijkstra 求解或在曼哈顿 BFS 的情况下）
根据特定时间，考虑交通和红绿灯，选择曼哈顿从 X、Y 角到 X1、Y1 角的最佳路线（因此边 1,1 的成本有显着差异到 1,2 如果你在 t0 到达 1,1 并且如果你在 t1 > t0 到达 1,1，例如：那部分路在 t1 被阻塞 10 小时）。
我正在调试遗留代码，其中道路网络已由 Boost Graph 表示。
A_Star 搜索没有给我两个特定点之间的最短路径，我知道 boost 不会错（直到我调试了我的代码一千次）。
要手动调试，我需要知道如何打印2 个顶点之间的所有可能路径。在我的输出中，每条路径都应由一系列边及其相应的权重表示。
我很重视您的帮助和评论
A* 基于启发式。如果遗留使用 A*，则意味着问题更复杂，然后只需找到最短路径即可。
要找到2个顶点之间的最短路径，有一些图算法，Dijkstra是最容易实现的（确保同时进行循环检查）。这些是确定性的。
如果您需要知道 2 个顶点之间的所有路径，这个是 NP 完全路径，这意味着您需要进行回溯。
A*一般用来解决NP完全问题。结果不是最好的路径，只是在适当的时间内找到的一条非常好的路径。
A* 的启发式算法用于放弃递归或将算法从回溯法转换为广度优先搜索法（通常是后者）。
A* 算法和 Dijkstra 算法可解决的问题之间的差异示例如下（来自我的头脑）：
在曼哈顿找到从 X、Y 角到 X1、Y1 角的最短路线（可由 Dijkstra 求解或在曼哈顿 BFS 的情况下）
根据特定时间，考虑交通和红绿灯，选择曼哈顿从 X、Y 角到 X1、Y1 角的最佳路线（因此边 1,1 的成本有显着差异到 1,2 如果你在 t0 到达 1,1 并且如果你在 t1 > t0 到达 1,1，例如：那部分路在 t1 被阻塞 10 小时）。