Dijkstra Algorithm on a graph modeling a network

Question

We have a directed graph G = (V, E) for a comm. network with each edge having a probability of not failing r(u, v) (defined as edge weight) which lies in interval [0, 1]. The probabilities are independent, so that from one vertex to another, if we multiply all probabilities, we get the the probability of the entire path not failing.

I need an efficient algorithm to find a most reliable path from one given vertex to another given vertex (i.e., a path from the first vertex to the second that is least likely to fail). I am given that log(r · s) = log r + log s will be helpful.

This is what I have so far -:

DIJKSTRA-VARIANT (G, s, t)
for v in V:
    val[v] ← ∞
A ← ∅
Q ← V to initialize Q with vertices in V.
val[s] ← 0
while Q is not ∅ and t is not in A
    do x ← EXTRACT-MIN (Q)
    A ← A ∪ {x}
    for each vertex y ∈ Adj[x]
        do if val[x] + p(x, y) < val[y]:
           val[y] = val[x] + p(x, y)

s is the source vertex and t is the destination vertex. Of course, I have not exploited the log property as I am not able to understand how to use it. The relaxation portion of the algorithm at the bottom needs to be modified, and the val array will capture the results. Without log, it would probably be storing the next highest probability. How should I modify the algorithm to use log?

Answer 1

Right now, your code has

do if val[x] + p(x, y) < val[y]:
    val[y] = val[x] + p(x, y)

Since the edge weights in this case represent probabilities, you need to multiply them together (rather than adding):

do if val[x] * p(x, y) > val[y]:
    val[y] = val[x] * p(x, y)

I've changed the sign to >, since you want the probability to be as large as possible.

Logs are helpful because (1) log(xy) = log(x) + log(y) (as you said) and sums are easier to compute than products, and (2) log(x) is a monotonic function of x, so log(x) and x have their maximum in the same place. Therefore, you can deal with the logarithm of the probability, instead of the probability itself:

do if log_val[x] + log(p(x, y)) > log_val[y]:
    log_val[y] = log_val[x] + log(p(x, y))

Edited to add (since I don't have enough rep to leave a comment): you'll want to initialize your val array to 0, rather than Infinity, because you're calculating a maximum instead of a minimum. (Since you want the largest probability of not failing.) So, after log transforming, the initial log_val array values should be -Infinity.

Answer 2

In order to calculate probabilities you should multiply (instead of add) in the relaxation phase, which means changing:

do if val[x] + p(x, y) < val[y]:
           val[y] = val[x] + p(x, y)

to:

do if val[x] * p(x, y) < val[y]:
           val[y] = val[x] * p(x, y)

Using the Log is possible if the range is (0,1] since log(0) = -infinity and log(1) = 0, it means that for every x,y in (0,1]:
probability x < probability y than:
log(x) < log(y).
Since we are maintaining the same relation (between probabilities) this modification will provide the correct answer.

I think you'll be able to take it from here.

Answer 3

I think I may have solved the question partially.

Here is my attempt. Edits and pointers are welcome -:

DIJKSTRA-VARIANT (G, s, t)
for v in V:
    val[v] ← 0
A ← ∅
Q ← V to initialize Q with vertices in V.
val[s] ← 1
while Q is not ∅ and t is not in A
    do x ← EXTRACT-MAX (Q)
    A ← A ∪ {x}
    for each vertex y ∈ Adj[x]
        do if log(val[x]) + log(p(x, y)) > log(val[y]):
           log(val[y]) = log(val[x]) + log(p(x, y))

Since I am to find the highest possible probability values, I believe I should be using >. The following questions remain -:

1. What should the initial values in the val array be?

2. Is there anything else I need to add?

EDIT: I have changed the initial val values to 0. However, log is undefined at 0. I am open to a better alternative. Also, I changed the priority queue's method to EXTRACT-MAX since it is the larger probabilities that need to be extracted. This would ideally be implemented on a binary max-heap.

FURTHER EDIT: I have marked tinybike's answer as accepted, since they have posted most of the necessary details that I require. The algorithm should be as I have posted here.