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)\}\)


    \(\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 \).

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email