Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to reformulate this to a shortest-path problem?

If both nodes and edges are weighted, is it still possible to find a min-weight path?

  • $\begingroup$ Just split vertices into a new edge with the vertex weight the new edge weight. $\endgroup$ – Nicholas Mancuso Jan 27 '13 at 21:57

You can treat this as a directed graph problem, where the weights of all edges coming into a node are equal to that node's weight.

If the edges are weighted too, add the node's weight and the edge's weight together to find the incoming edge's weight in the directed graph.

  • $\begingroup$ And this is essentially solvable by shortest path algorithm in P time ? (if there is no cycle) $\endgroup$ – user1652 Jan 12 '18 at 16:25

The question can be posed as a branch-and-bound problem.

Perform a breadth-first search, extending the path with the smallest incremental increase in cumulative weight. Terminate any paths that reach already seen nodes. Continue until you reach the desired destination node.

Given that you have no geometric measure, the search can, in the worst case, result in a crawl of the entire graph. If you any distance measure to the destination from each node, use that to select the next hop to explore.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.