Algorithm to find shortest lightest path in a graph from source

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 step 1

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?

The whole point about Dijkestra is that it finds the best path on it's own. You don't need BFS. In fact, Dijkestra is sort of a BFS.

Use tuples as weigths. Then your question becomes simply "find the lightest path".

How it works on your graph:

Start with a lists of undiscovered vertices and discovered ones. I labeled the unlabeled vertices E and F. I use tuples length, edgeweigth as weigth in terms of Dijkestra.

undiscovered
[B, C, D, E, F]

discovered (length, edgeweigth)
A (0, 0)

Enumerate all paths from discovered vertices to undiscovered ones along with the resulting weigth

A -(1)-> B (1, 1)
A -(1)-> C (1, 1)
A -(0)-> E (1, 0)  <

Find the best one according to your objective function. In your case: smaller length, on equal length smaller edgeweight. Add it to the discovered vertices.

Iteration 1

undiscovered
[B, C, D, F]

discovered (length, edgeweigth)
A (0, 0)
E (1, 0)

Paths
A -(1)-> B (1, 1)   C (1, 1)

Iteration 2

undiscovered
[C, D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
E (1, 0)

Paths
A -(1)-> C (1, 1)   D (2, 11)

Iteration 3

undiscovered
[D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)

Paths
C -(1)-> D (2, 2)
C -(0)-> F (2, 1)   D (2, 11)

Iteration 4

undiscovered
[D]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)
F (2, 1)

Paths
C -(1)-> D (2, 2)   D (2, 11)

Iteration 5

undiscovered
[]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
D (2, 2)
E (1, 0)
F (2, 1)

No more undiscovered vertices -> we're done.

StackExchange Computer Science Q#51721, answer score: 3