inactive. We simply check whether $L(S)-f_2(e)>L(D)$, and if this is true then the vertex $D$ gets its label updated to $L(S)-f_2(e)$ and its status changed to [*active*]{}. If the vertex $D$ was active, the situation is more complicated, since the water has already started flowing from the vertex $D$. The existing water flows correspond to water of quality worse than the new water that has just arrived to $D$. We resolve this issue by introducing phantom edges to the graph that are parallel to the existing edges. The phantom edges will carry this new high quality water, while old edges will continue carrying their old water flows. A point stops being active if all of its edges become used, but it may get activated again in the future.

The assignment of phantom edges to the vertices of the graph and their removal is considered a label correcting approach in solving the problem. Our particular choice of label correction is designed for large graphs in which the vertices have bounded degree. Several existing serial computation algorithms can find the shortest path by maintaining labels for all vertices. The labels are used to store the information on the shortest path from the 