Algorithm to find shortest lightest path in a graph from source

Question

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:

1. run BFS on $G$ from source $s$
2. 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?

Answer 1

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)  <
A -(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)  <
B -(10)-> 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)  <
B -(10)-> 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)  <
B -(10)-> 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.

Answer 2

A single BFS suffices. No need to use Dijkstra's SSSP algorithm (wiki). In the following, I suppose that you are somewhat familiar with the "white-gray-black", queue-based framework for BFS. If not, please refer to CLRS or this online lecture note. The explanation of the pseudocode is included in the comments.

Enqueue(Q,s)
while (Q not empty)
  do u <- Dequeue(Q)                   // focus on node u
    For each v in adj[u]               // for each adjacent node v of u, do the something below according to its color (i.e., state)
      do if color[v] == White          // first discovered
         then   d[v] = d[u] + w(u->v)  // calculate path weight for v; which may be updated later; see below
                color[v] = Gray        // color v Gray
                Enqueue(Q,v)           // enqueue v
        elseif  color[v] == Gray       // already in the queue
                d[v] = min(d[v], d[u] + w(u->v))  // update path weight for v if necessary
        else    // color[v] == Black  // has been finished
                do nothing
   color[u] = Black                   // finished u