我应该使用什么算法来获得有向加权图中所有可能的路径，权重为正？
What algorithm should I use to get all possible paths in a directed weighted graph, with positive weights?
我有一个有向加权图，权重为正，看起来像这样:-
我想做的是：-
- 找到两个节点之间的所有可能路径。
- 根据路径长度（由边权重给定）按升序排列路径，至少说前 5 条。
- 采用最优方式，即使在节点数较多的情况下，程序也不会耗费太多时间进行计算。
例如：- 假设我的初始节点是 d，最终节点是 c。
所以输出应该是这样的
d to c = 11
d to e to c = 17
d to b to c = 25
d to b to a to c = 31
d to b to a to f to c = 38
我怎样才能做到这一点？
Find all possible paths between two nodes
您可以在此处使用暴力破解，但您可能会得到很多路径，而且绘制更大的图（>100 个节点，取决于很多因素）确实需要数年时间。
Arrange the paths in ascending order, based on their path length (as given by the edge weights), say top 5 atleast.
简单排序，先取5。 （您可以结合使用边列表和路径长度的 integer/double）。
Use an optimal way to do so, so that even in cases of larger number of nodes, the program won't take much time computing.
即使找到两个节点之间所有可能的路径也是NP-Hard (Source, it's for undirected graphs, but is still valid). You will have to use heuristics.
更多节点是什么意思？你是说100还是1亿？这取决于您的上下文。
最好的方法是采用Dijkstra’s shortest path算法，我们可以在O(E + VLogV)时间内得到最短路径。
采用这种基本方法来帮助您找到可能的最短路径：
查看与起始节点直接相邻的所有节点。连接起点和这些相邻节点的边所携带的值是到每个相应节点的最短距离。
记录节点上的这些距离 - 覆盖无穷大 - 并划掉节点，这意味着已找到它们的最短路径。
Select 已计算出最短路径的节点之一，我们将其称为枢轴。查看与其相邻的节点（我们将这些称为我们的目标节点）以及它们之间的距离。
对于每个结局（目的地节点）：
如果枢轴中的值加上连接它的边值总和小于目标节点的值，则更新其值，因为已找到新的更短路径。
如果到该目的节点的所有路径都被探索过，则可以划掉。
重复步骤2，直到所有节点都被划掉。我们现在有一个图表，其中任何节点中保存的值将是从起始节点到它的最短距离。
我有一个有向加权图，权重为正，看起来像这样:-
我想做的是：-
- 找到两个节点之间的所有可能路径。
- 根据路径长度（由边权重给定）按升序排列路径，至少说前 5 条。
- 采用最优方式，即使在节点数较多的情况下，程序也不会耗费太多时间进行计算。
例如：- 假设我的初始节点是 d，最终节点是 c。 所以输出应该是这样的
d to c = 11
d to e to c = 17
d to b to c = 25
d to b to a to c = 31
d to b to a to f to c = 38
我怎样才能做到这一点？
Find all possible paths between two nodes
您可以在此处使用暴力破解，但您可能会得到很多路径，而且绘制更大的图（>100 个节点，取决于很多因素）确实需要数年时间。
Arrange the paths in ascending order, based on their path length (as given by the edge weights), say top 5 atleast.
简单排序，先取5。 （您可以结合使用边列表和路径长度的 integer/double）。
Use an optimal way to do so, so that even in cases of larger number of nodes, the program won't take much time computing.
即使找到两个节点之间所有可能的路径也是NP-Hard (Source, it's for undirected graphs, but is still valid). You will have to use heuristics.
更多节点是什么意思？你是说100还是1亿？这取决于您的上下文。
最好的方法是采用Dijkstra’s shortest path算法，我们可以在O(E + VLogV)时间内得到最短路径。
采用这种基本方法来帮助您找到可能的最短路径：
查看与起始节点直接相邻的所有节点。连接起点和这些相邻节点的边所携带的值是到每个相应节点的最短距离。
记录节点上的这些距离 - 覆盖无穷大 - 并划掉节点，这意味着已找到它们的最短路径。
Select 已计算出最短路径的节点之一，我们将其称为枢轴。查看与其相邻的节点（我们将这些称为我们的目标节点）以及它们之间的距离。
对于每个结局（目的地节点）： 如果枢轴中的值加上连接它的边值总和小于目标节点的值，则更新其值，因为已找到新的更短路径。 如果到该目的节点的所有路径都被探索过，则可以划掉。
重复步骤2，直到所有节点都被划掉。我们现在有一个图表，其中任何节点中保存的值将是从起始节点到它的最短距离。