The Algorithm Design Manual Second Edition

Stop and Think: Shortest Path with Node Costs

Problem: Suppose we are given a graph whose weights are on the vertices, instead

of the edges. Thus, the cost of a path from x to y is the sum of the weights of all

vertices on the path.

Give an efficient algorithm for finding shortest paths on vertex-weighted graphs.

Solution: A natural idea would be to adapt the algorithm we have for edge-weighted

graphs (Dijkstra’s) to the new vertex-weighted domain. It should be clear that we

can do it. We replace any reference to the weight of an edge with the weight of

the destination vertex. This can be looked up as needed from an array of vertex

weights.

However, my preferred approach would leave Dijkstra’s algorithm intact and

instead concentrate on constructing an edge-weighted graph on which Dijkstra’s

tree rooted in s. For unweighted graphs, this would be the breadth-first search tree,

---

210

6 .

W E I G H T E D G R A P H A L G O R I T H M S

algorithm will give the desired answer. Set the weight of each directed edge (i, j)

in the input graph to the cost of vertex j. Dijkstra’s algorithm now does the job.

This technique can be extended to a variety of different domains, such as when

there are costs on both vertices and edges.