8
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Just split vertices into a new edge with the vertex weight the new edge weight. $\endgroup$
    – Nicholas Mancuso
    Jan 27, 2013 at 21:57

2 Answers 2

Reset to default
7
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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