0

我知道找到最长的路径是一个 NP Hard 问题。

我们要求我们改变 Dijkstra 的算法，通过在算法中添加另一个参数来找到最长的路径。一个参数，如从源到给定顶点的距离、顶点的前任、后继、边数……例如，我们可以根据最大距离以外的参数从队列中提取顶点，或者我们可以另一个队列...

我们首先要做的是改变初始化，使除了源节点之外的所有顶点距离 = 0，即 = 无穷大。然后我们从顶点队列中提取距离最大的顶点。然后，我们反转松弛符号，这样如果顶点大于当前距离，则保存距离。

我可以添加什么参数来提高 Dijkstra 在查找最长路径时的性能？它不必在 100% 的时间内工作。

这是 Dijkstra 的算法：

ShortestPath(G, v)
  init D array entries to infinity
  D[v]=0
  add all vertices to priority queue Q
  while Q not empty do
     u = Q.removeMin()
     for each neighbor, z, of u in Q do
       if D[u] + w(u,z) < D[z] then
          D[z] = D[u] + w(u,z)
          Change key of z in Q to D[z]
 return D as shortest path lengths

这是我们的修改版本：

 ShortestPath(G, v)
   init D array entries to 0
   D[v]=infinity //source vertex
   add all vertices to priority queue Q
   while Q not empty do
     u = Q.removeMax()
     for each neighbor, z, of u in Q do
        if D[u] + w(u,z) > D[z] then
          D[z] = D[u] + w(u,z)
          Change key of z in Q to D[z]
   return D as shortest path lengths
4

0 回答 0