performance - 在具有节点和边权重的图中找到最短路径？

Question

假设我有一个加权图，边和顶点都有权重。如何找到从某个节点 s 到某个节点 t 的“最便宜”路径？我的复杂度应该是 O(n ² (n+m))。

Answer 1

解决这个问题的一种方法是将图形转换为一个新的图形，其中只有边被加权，而不是顶点。为此，您可以将每个节点拆分为两个节点，如下所示。对于任何节点 v，创建两个新节点 v ₁和 v ₂。之前进入节点 v 的所有边现在都进入节点 v ₁，所有离开节点 v 的边现在都离开 v ₂。然后，在 v ₁和 v ₂之间放置一条边，其成本是节点 v 的成本。

在这个新图中，从一个节点到另一个节点的路径成本对应于原始图中原始路径的成本，因为仍然支付所有边权重，并且现在使用新插入的边支付所有节点权重。

构建这个图应该在 O(m + n) 时间内是可行的，因为您需要将每条边恰好更改一次，并且每个节点只更改一次。从那里，您可以使用普通的 Dijkstra 算法在 O(m + n log n) 时间内解决问题，给出 O(m + n log n) 的整体复杂度。如果存在负权重，则可以改用 Bellman-Ford 算法，总复杂度为 O(mn)。

希望这可以帮助！

Answer 2

我认为可以在我们只有边加权的图 G' 中转换该图 G。转换的算法非常简单，因为我们对边和节点都进行了加权，所以当我们从 A -> B 移动时，我们知道从 A 移动到 B 的总权重是边的权重（A -> B）加上权重B 本身，所以让这两个权重的 A -> B 边权重和 B 的权重为零。比我们可以找到从任何节点 s 到任何节点到 O(mlogn) 的最短路径，其中（n - 节点数，m - 边数）

Answer 3

修改Djkstra 后 应该可以工作

  1  function Dijkstra(Graph, source):
     2      for each vertex v in Graph:                                // Initializations
     3          dist[v] := infinity ;                                  // Unknown distance function from 
     4                                                                 // source to v
     5                                                                 // Previous node in optimal path
     6      end for                                                    // from source
     7      
     8      dist[source] := source.cost ;                                        // Distance from source to source
     9      Q := the set of all nodes in Graph ;                       // All nodes in the graph are
    10                                                                 // unoptimized - thus are in Q
    11      while Q is not empty:                                      // The main loop
    12          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
    13          remove u from Q ;
    14          if dist[u] = infinity:
    15              break ;                                            // all remaining vertices are
    16          end if                                                 // inaccessible from source
    17          
    18          for each neighbor v of u:                              // where v has not yet been 
    19                                                                 // removed from Q.
    20              alt := dist[u] + dist_between(u, v)+v.cost ;
    21              if alt < dist[v]:                                  // Relax (u,v,a)
    22                  dist[v] := alt ;
    23                                 
    24                  decrease-key v in Q;                           // Reorder v in the Queue
    25              end if
    26          end for
    27      end while
    28  return dist;