Consider a diagram of a telephone network, which is a graph G whose vertices rep

Question

Consider a diagram of a telephone network, which is a graph G whose vertices represent switching centers, and whose edges represent communication lines joining pairs of centers. Edges are marked by their bandwidth, and the bandwidth of a path is the bandwidth of its lowest bandwidth edge. Give an algorithm that, given a diagram and two switching centers a and b, outputs the maximum bandwidth of a path between a and b.

Explanation / Answer

Algorithm: Maximum Bandwidth(G,a) Input: A simple undirected weighted graph G with non -ve edge weights, and a distinguished vertex a of G Output: A label D[u], for each vertex u of G, such that D[u] is the maximum bandwidth available from a to u. Initialize empty queue Q; Start = a; for each vertex u of G do, D[u] = 0; for all vertices z adjacent to Start do{ ---- 1 If D[Start] => D[z] && w(start, z) > D[z] { Q.enqueue(z); D[z] = min(D[start], D[z]); } } If Q!=null { Start = Q.dequeue; Jump to 1 } else finish();

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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