<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2018-01-12T16:25:53.670Z
And this is essentially solvable by shortest path algorithm in P time ? (if there is no cycle)
user1652
CC BY-SA 3.0
2013-01-25T18:47:13.250Z
2013-01-25T19:19:13.183Z
2013-01-25T19:19:13.183Z
BlueRaja - Danny Pflughoeft
<p>The question can be posed as a <a href="http://xlinux.nist.gov/dads/HTML/branchNbound.html" rel="nofollow">branch-and-bound</a> problem.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-01-26T14:12:48.660Z
2013-01-26T14:12:48.660Z
Pekka
<p>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?</p>

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

CC BY-SA 3.0
2013-01-27T21:57:08.143Z
Just split vertices into a new edge with the vertex weight the new edge weight.
Nicholas Mancuso
<graph-algorithms><shortest-path>
Finding a minimum "node" weight path
Chang
# Finding a minimum "node" weight path

(Asked by: username_0 on 2013-01-25)

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?

**Tags:** graph-algorithms, shortest-path
> **Comments:**
> **username_1**: Just split vertices into a new edge with the vertex weight the new edge weight.  

---

## 2 answers

### Answer by username_2 on 2013-01-25. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_3**: And this is essentially solvable by shortest path algorithm in P time ? (if there is no cycle)  

---

### Answer by username_4 on 2013-01-26. Score: -1

The question can be posed as a [branch-and-bound](http://xlinux.nist.gov/dads/HTML/branchNbound.html) 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.


---

