Vertex weights
Task number: 4165
Let us have a vertex weighted graph, i.e. the graph \( G = (V, E) \) and the weight function \( w: V \to \mathbb R^+ \). The weight of the path is the sum of the weights of the vertices through which the path passes. Modify Dijkstra’s algorithm to find the path of the smallest weight between two given vertices.
Solution
In Dijkstra’s algorithm, it is sufficient to change the update of the distance estimate \( d \) from
\(\forall y\in N(x): d(y)=\min\{d(y),d(x)+l(x,y)\}\)
to
\(\forall y\in N(x): d(y)=\min\{d(y),d(x)+w(y)\}\).
As in Dijkstra’s algorithm, we adjust the estimate if \( y \) can be better accessed via \( x \).
