遍历所需边缘列表的最短路径

Question

我有一个有向图,看起来像这样:

我想找到从开始到结束最便宜的路径,其中橙色虚线都是路径有效所必需的.

自然最短路径是:开始 - > A - > B - >结束,结果成本= 5,但我们没有满足所有必需的边访问.

我想要找到的路径(通过一般解决方案)是开始 - > A - > B - > C - > D - > B - >结束,其中成本= 7,我们已经满足所有必需的边访问.

有没有人对如何要求这样的边缘遍历有任何想法？

Answer 1

令R为所需边的集合，且F = | R |。设G为输入图t（分别为s）为请求路径的起始点（分别为结束点）。

\n\n\n\n

预处理：运行一堆 Dijkstra 算法...

\n\n

第一步是创建另一个图表。该图将恰好有F +2 个顶点：

\n\n

\n
• R中的每条边各一个
\n
• 其中之一表示要计算的路径的起点t
\n
• 其中之一表示要计算的路径的终点s
\n

\n\n

要创建此图表，您必须执行以下操作：

\n\n

\n
1. 从G中删除R中的每条边。
\n
2. 对于R中的每条边E = ( b,e ) ：\n
   \n
   1. 计算从t到b 的最短路径以及从e到s的最短路径。如果存在，则在“新图”中添加一条将s连接到E 的边，权衡相关最短路径的长度。
   \n
   2. 对于R \\ { E } 中的每条边E\' = ( b\', e\' ) :\n
      \n
      1. 计算从e到b\'的最短路径。如果存在，则在新图中添加一条从E到E\'的边，并衡量该最短路径的长度。将计算出的路径作为有效负载附加到相关边缘。
      \n
      2. 将计算出的路径作为有效负载附加到该边缘
      \n
   \n
\n

\n\n

构建此图的复杂度为O((F+2)\xc2\xb2.(E+V).log(V))，其中E（分别V）是原始图像中边（分别是顶点）的数量图形。

\n\n\n\n

详尽搜索最佳可能路径

\n\n

从这一点开始，我们必须在新创建的图中找到最短的哈密顿路径。不幸的是，这个任务是一个难题。我们没有比探索每一条可能的路径更好的方法了。但这并不意味着我们不能巧妙地做到这一点。

\n\n

我们将使用回溯来执行搜索。我们可以通过维护两个集合来实现这一点：

\n\n

\n
• 当前探索的顶点列表：K（K代表已知）
\n
• 当前未知顶点的列表：U（U代表未知）
\n

\n\n

在深入研究算法定义之前，先介绍一下主要思想。除了探索新图中可能路径的整个空间之外，我们别无选择。每一步，我们都必须做出决定：下一步我们该采取哪条优势？这会导致一系列决策，直到我们无法再移动或达到s为止。但现在我们需要回去取消决定，看看是否可以通过改变方向做得更好。要取消决定，我们按如下方式进行：

\n\n

\n
• 每当我们陷入困境（或找到一条路）时，我们都会取消上次做出的决定
\n
• 每次我们在某个时刻做出决定时，我们都会跟踪哪个决定，因此当我们回到这一点时，我们知道不要做出同样的决定并探索其他可用的决定。
\n
• 我们可能会陷入困境，因为：\n
  \n
  • 我们找到了一条路。
  \n
  • 我们无法进一步移动（没有我们可以探索的边缘，或者我们唯一可以采取的边缘使当前的部分路径增加太多——它的长度变得比当前找到的最佳路径的长度更高）。
  \n
\n

\n\n

最终的算法可以这样总结：（我给出了一个迭代实现，人们可以找到一个更容易和更清晰的递归实现）

\n\n

设K\xe2\x86\x90 []、L[0..R+1]\xe2\x86\x90[]和U\xe2\x86\x90 V （其中 V 是工作图中每个顶点减去起始和结束顶点t和s的集合）。最后让l\xe2\x86\x90 i\xe2\x86\x90 0 和best_path_length\xe2\x86\x90 \xe2\x88\x9e 和best_path\xe2\x86\x90[]

\n\n

而（i\xe2\x89\xa5 0）：

\n\n

\n
1. 而U\xe2\x89\xa0 []\n
   \n
   1. c\xe2\x86\x90 U.popFront()（我们取U的头）
   \n
   2. L[i].pushBack(c)
   \n
   3. 如果i == R+1AND ( l== 权重( cur_path.back(), s ) + l) < best_path_length:\n
      \n
      1. best_path_length\xe2\x86\x90l
      \n
      2. 最佳路径\xe2\x86\x90cur_path
      \n
   \n
   4. K.tail()如果和之间有一条边 e c，并且weight(e)+ l< best_path_length:（如果K为空，则替换K.tail()为上一条语句中的t ）\n
      \n
      1. K.pushBack(c)
      \n
      2. i\xe2\x86\x90 i+1
      \n
      3. l\xe2\x86\x90 weight(e)+l
      \n
      4. cur_path.pushBack(c)
      \n
   \n
\n
2. L[i]在末尾连接U
\n
3. L[i]\xe2\x86\x90[]
\n
4. i\xe2\x86\x90 i-1
\n
5. cur_path.popBack()
\n

\n\n

在 while 循环 ( ) 结束时while (i \xe2\x89\xa5 0)，best_path将保留最佳路径（在新图中）。从那里，您只需获取边的有效负载即可重建原始图中的路径。

\n