Given a directed graph $ G = (V,E)$ with non-negative(zero and positive) weights on the edges, and a vertex $ s \in V $
Problem: Find the lightest path from $s $ to each and every vertex $v \in V$ and that's from the shortest paths from $ s$ to all $v \in V$
Length of a path is the number of edges in the path.
Weight of a path is the sum of all weights of the path's edges
-------- Edit: Elaborating the question: --------
Suppose there are $x$ different paths between $s$ and some $v \in V$. Each path has its own weight. Among those $x$ paths, there are $y$ shortest paths(pay attention $ y \subseteq x$ and all the paths in $y$ have the same length).
What I'm trying to find: The lightest path among the above $y$ paths. Also, i want to calculate that weight for every vertex in $V$.
Initially, i thought about this algorithm:
- run BFS on $G$ from source $s$
- run Dijkestra on the BFS tree from
However, i ran into this problem:
With source vertex $A$, the red path and the black path, both lead to the same vertex $D$.
Pay attention how $ A\rightarrow B\rightarrow D$ and $A \rightarrow C \rightarrow D$ are both of length 2 Although they are both the shortest paths from $A$ to $D$, the red path is lighter than the black one.
I thought about 'tweaking' BFS:
Each time i arrive at a vertex $v$ which i already discovered, i check whether the "new" path i already walked to $v$ is lighter than the one already set to $v$.
However, i don't want to change in the algorithm, because i need to prove that it actually work from the start.
How can i modify my algorithm so that the problem i pointed won't pop-out?