Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all outgoing edges $vu$ is the same.
How can one modify Dijkstra's algorithm so that exactly one relaxation is done for every vertex $v \in V$? (i. e. decreasing of current minimal path length $d_{v}$ is done exactly once for every $v$).
In each iteration, instead of choosing the node $u$ with smallest $\mathtt{dist}[u]$ in the standard Dijkstra's algorithm, we choose the node $u$ with smallest $\mathtt{dist}[u]+w(u)$, where $w(u)$ is the weight of outgoing edges from $u$.
The proof of the correctness of this modified algorithm is almost the same as the one of the standard Dijkstra's algorithm. As shown in the proof for the standard Dijkstra's algorithm, it also holds that for each visited node $v$, $\mathtt{dist}[v]$ is the shortest distance from source to $v$.
Now consider a node $v$. Let $P$ be a shortest path from source to $v$. Suppose $\mathtt{dist}[v]$ is first updated through $u$ (i.e., it is updated to $\mathtt{dist}[u]+w(u)$), and when $\mathtt{dist}[v]$ is first updated, $x$ is the first unvisited node on $P$, then $\mathtt{dist}[x]+w(x)\le w(P)\le \mathtt{dist}[u]+w(u)$, where $w(P)$ is the shortest distance from source to $v$. Also note at this time $u$ is chosen instead of $x$, we have $\mathtt{dist}[u]+w(u)\le \mathtt{dist}[x]+w(x)$, hence $\mathtt{dist}[x]+w(x)= w(P)= \mathtt{dist}[u]+w(u)$, i.e., $\mathtt{dist}[v]$ is first updated to the shortest distance from source to $v$, and it will not be updated any more.
