初等最短路径问题与最短路径问题

Question

基本最短路径问题和最短路径问题有什么区别？

一个最短路径问题，通过在图中找到从源节点到目标节点t的最短路径来解决。

一个简单的最短路径问题，通过在图中找到从源节点到目标节点t的最短路径，使得最短路径上的每个弧最多使用1次。

什么是基本的最短路径？

Answer 1

术语“基本最短路径”是指“不重复任何节点或边缘的最短路径”。如果你想在没有负循环的图中计算从一个节点到另一个节点的最短路径，那么“最短路径”和“基本最短路径”没有区别，因为它们的意思是相同的。然而，在其他情况下，“最短路径”可能与“基本最短路径”不同。例如：

• 如果您的目标是找到一条从某个节点开始，到某个节点t结束的路径，并在此过程中访问某个集合X中的所有节点，那么这样做的最短路径可能与基本最短路径不同。根据图的形状，甚至可能没有一条基本的最短路径来实现这一目标。如果图有负循环，那么“从s到t的最短路径”的概念在数学上可能没有很好的定义，因为一遍又一遍地遵循负循环会不断降低成本。但是，只要有从s到t的路径，就可以定义“基本最短路径”，因为不能遵循负循环。

希望这能有所帮助！