Please helps with exercise 12.5 Exercise 12.5. A communications provider has a n

Question

Please helps with exercise 12.5

Exercise 12.5. A communications provider has a number of computers that are connected using a network. Assume that the network is an undi rected graph G- (V, E) where the vertices represent the computers and the edges represent the links between them. Each edge (u, v) E has an associated weight b(u, v) (a positive number) which represents the band width capacity of that edge. Given a path between two nodes, the bottle- neck value of the path is the minimum of the weights of the edges in the path. The maximum bottleneck path between two nodes is the path that has the maximum bottleneck value among all paths between them. (a) In the graph of Figure 12.2, compute the respective maximum bot tleneck paths between node a and all other nodes. (b) Develop an algorithm that given two nodes a and b computes the maximum bottleneck value path from a to b. What is the running time of your algorithm. (Hint: Modify Dijkstra's algorithm to solve this problem.) Figure 12.2: A weighted graph and its shortest path tree (SPT), rooted at node c.

Explanation / Answer

From a to b=2

From a to c=5

From a to d=5+7=12

From a to e=5+7+8=20

From a to f=5+7+8+20=40

From a to g=2+2=4

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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