Given a network conguration, assume that you want to nd the most reliable paths

Question

Given a network conguration, assume that you want to nd the most reliable paths from a given node to all the other nodes. Assume that you know the probability of an error for each link, and the reliability of a path is given by the probability that none of the links that belong to the given path is in error. As usual, assume that links are all independent. (a) Explain why you cannot simply use Dijkstra’s algorithm or Bellman-Ford algorithm as is to nd the most reliable paths.

(b) Explain how to modify Dijkstra’s algorithm or Bellman-Ford algorithm to do so. Note that modications to the algorithms may be slightly dierent.

Explanation / Answer

most relaiable path:The path in which the probability of error is less.
prob of error=product of error probabilities of eac edge in the path.
a) We cant use Dijkstra’s algorithm directly because the comparision step in the algorithm contain addition rather than multiplication.
b) We can change the algorithm by changing addition to multiplication or bu using -log(prob) as they are additive .

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.