加权图-查找最大停止点从X到y的所有路径

Question

我正在一个Java项目上，除其他事项外，该项目需要使用最大停止数返回从x到y的所有可能路径。

例如，每个节点都是一个城市，从一个城市到另一个城市的每条路径都具有成本值。

我正在通过参考使用本文，这是我使用的相同模型。 http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html

将最短的路径从x返回到Y可以正常工作，但是我需要每种路径的所有可能路径和成本。

例如：

在给定的最大停靠点数内查找来自任何给定的一对城镇的所有可用路线。

输入图：AB5，BC4，CD8，DC8，DE6，AD5，CE2，EB3，AE7

从C到C的路线，最多3站：

CDC（2站）CEBC（3站）

从A到C的路线，最多4站：

ABC（2停）ADC（2停）AEBC（3停）ADEBC（4停）

Answer 1

老实说，我会用BFS代替Dijkstra。您不是在寻找最短路径，而是任何路径。因此，您可以只在节点x上运行BFS，然后执行k步（我将最大步数称为k）即可停止它。每次到达y时，都可以将路径添加到答案中。

Answer 2

每个节点链接的权重就是两者之间的距离。例如）A-> 7-> B-> 3 ---> C --->等等...在这种情况下，从A到C的路径的总权重将是每个坐标之间所有权重（距离）的总和。低于最大值的所有可能路径都可以通过上述计算方式记录下来