单源路径问题

Question

单源路径是指起始点是固定的，那么这个固定点怎么理解，比如说我从4到6，它的起始点不是4吗，6是终止点，那这样的话，起始点不是被改变了吗？单源的意思是不是初始态下指定一个起始点，那么这个起始点就被固定了，在这个过程中，终止节点是可以随便指定的，只是在这一次过程中起始点是被固定了，下次重新指定起始点，那么它还是会改变的？

Answer 1

liuyubobobo 2022-06-22 02:36:51

单源路径的意思是，这个起始点（即所谓的单源），是算法的一个参数，指定一个图 g，和一个起始点 s，运行单源路径算法，将可以求出这个图中，以 s 为起点，其他点为终点的路径。但是，这个过程中不能得到以其他点为起点的路径。

如果你想在同样的图中求出以 u 为起点的路径，就要将 u 作为参数传给算法，重新运转一遍算法。

这就是为什么，在我们的算法类中，创建这个算法类的参数出了图 G 以外，还需要一个起始点 s。这个指定的 s，就是单源路径中的这个“单源”：https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/04-Graph-DFS-Applications/05-Single-Source-Path/src/SingleSourcePath.java

继续加油！：）

• 提问者 qq_crusader_1 #1

  懂了，谢谢老师，你后面那个实现点对路径的就证实了这一点