Finding a shortest path in a graph with node and e

问题:

Let's say I have a weighted graph with weights on both edges and vertices. How do I find the "cheapest" path from a certain node s to a certain node t? My complexity should be O(n²(n+m)).

回答1:

One way to solve this would be to convert the graph into a new graph in which only edges are weighted, not vertices. To do this, you can split each node apart into two nodes as follows. For any node v, make two new nodes, v1 and v2. All edges that previously entered node v now enter node v1, and all edges that leave node v now leave v2. Then, put an edge between v1 and v2 whose cost is the cost of node v1.

In this new graph, the cost of a path from one node to another corresponds to the cost of the original path in the original graph, since all edge weights are still paid and all node weights are now paid using the newly-inserted edges.

Constructing this graph should be doable in time O(m + n), since you need to change each edge exactly once and each node exactly once. From there, you can just use a normal Dijkstra's algorithm to solve the problem in time O(m + n log n), giving an overall complexity of O(m + n log n). If negative weights exist, then you can use the Bellman-Ford algorithm instead, giving a total complexity of O(mn).

Hope this helps!

回答2:

Following modification of Djkstra should work

  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;

回答3:

I think it's possible to convert that graph G, in the graph G' where we have only edges weighted. The algorithm for converting is very simple, since we have both edges and nodes weighted, when we move from A -> B, we know that total weight to move from A to B is weight of edge(A -> B) plus weight of B itself, so lets make A -> B edge weight sum of these two weights and the weight of B zero. Than we can find shortest path from any node s to any node to in O(mlogn) where (n - number of nodes, m - number of edges)