Consider a directed graph G that has weights on nodes rather than links. In particular, for a node

v$,$ its weight is q$($v$).$ The node$-$weight of a path is the sum of the weights of the nodes along the path including

the source and destination nodes. The problem we$$d like to solve is to find the path from a source s to

destination t that has the smallest$-$node weight. Unfortunately, we don$$t have such an algorithm so we will repurpose our known shortest path algorithms.

Now let$$s suppose we have weights on the links. In particular, for a link $($u$,$v$),$ its weight is w$($u$,$v$).$ We will call

the sum of link weights along a path is the path$$s link$-$weight. Note that this is just our usual definition of the

path length in shortest path problems discussed in lecture. So we can use our shortest path algorithms to

solve them.