3
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ What do you mean by "shortest lightest"? Shortest for length? Lightest for weight? Consider a graph: A -(1)-> B -(10)-> E; A -(1)-> C -(1)-> D -(1)-> E. In this graph, A -> B -> E consists of 2 edges and weights 11; A -> C -> D -> E consists of 3 edges and however weights 3. Which one to choose? $\endgroup$ – hengxin Jan 11 '16 at 12:59
  • $\begingroup$ i mean: the lightest in weight among all the shortest in lengths between s and v. Means the priority here is for shortest in length, now, if there are few paths which satisfy the same short length, i want to pick the lightest among them. $\endgroup$ – ThunderWiring Jan 11 '16 at 13:50
  • $\begingroup$ I don't know what the phrase "and that's from the shortest paths from.." means. Can you edit the question to re-word and explain in a bit more detail? Also I don't understand what distinction you are drawing between lightest and shortest, or length and edge. Your input says you only have weights, but not lengths. Please revise the question to make this a lot clearer. $\endgroup$ – D.W. Jan 11 '16 at 16:32
  • $\begingroup$ The shortest path(referring to number of edges) between A(source) and D is of length 2. However, there are 2 different paths with length 2 from A to D which are the one in red and the one in black. Pay attention they are of different weight. see edit $\endgroup$ – ThunderWiring Jan 11 '16 at 17:02
  • $\begingroup$ The question makes no sense to me. The path in black (A-B-D) has length 1+10 = 11, as the picture shows the edge A-B having length 1 and the edge B-D having length 10. That's not length 2. I'm going to refer you to my previous comments. You are mixing the terms weight and length, and you need to decide whether you mean two different things (in which case you need to edit the question to clarify the setup) or mean the same thing (in which case you should stop doing that and use one word consistently rather than mixing two different words for the same thing). $\endgroup$ – D.W. Jan 11 '16 at 18:59
3
$\begingroup$

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".

The graph how it should be

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.
$\endgroup$
2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.