Telephone network is one of the network optimization problems. Diagram of any te

Question

Telephone network is one of the network optimization problems. Diagram of any telephone network shows a graph whose vertices represent switches centers, and whose edges represent communication lines between two centers. The network lines have bandwidth and routing the phone call is always done via the highest bandwidth.

In this project, you are about designing an algorithm that finds the maximum bandwidth of a path between any two switches centers.

Design and Analyze Algorithm: Routing Algorithm is the algorithm of finding maximum bandwidth path in a graph. It is based on modification of Dijkstra’s algorithm using a Heap structure. Write a clear pseudocode of routing algorithm, then analyze and find its time complexity. Implementation: You are permitted to use any programing environment and language to do the following:

• Generate the graph randomly with no less than 50 vertices and each vertex has edges incident to about 25% of the other vertices. Randomly assign positive weights to edges in the graphs.

• Include max-heap structure for maximum, insert, and delete methods. Since the heap structure you implement will be used for a Dijkstra algorithm in the routing operation. To simplify implementation, you can follow the suggestion below: Graph vertices are named by integers 1, 2, ...., n.

• Heap is declared as an array h[1..n], where each element h[i] saves the name of a vertex in the graph. • Vertex values are given in another array v[1..n]. Therefore, finding the value of a vertex h[i] in the heap, you can use v[h[i]].

1• Implement proposed routing algorithm using generated graph and max-heap subroutines as described above.

• You can get befit of programming environment libraries e.g. graph, priority queue.. Etc.

• visualize (draw) the original graph (randomly-generated graph) and resulting maximum path.

C# or java code is needed also

Explanation / Answer

The dual problem for the above numerical example is:

Max 1200U1 + 1000U2 + 800U3 + 1100V1 + 400V2 + 750V3 + 750V4

subject to:

U1 + V1 £ 35, U1 + V2 £ 30, U1 + V3 £ 40, U1 + V4 £ 32
U2 + V1 £ 37, U2 + V2 £ 40, U2 + V3 £ 42, U2 + V4 £ 25
U3 + V1 £ 40, U3 + V2 £ 15, U3 + V3 £ 20, U3 + V4 £ 28

all Ui and Vj are unrestricted in sign.

The dual formulation suggests that we try to ship the goods in such a way that the difference in unit price Ui at the ith origin and unit price Vj at the jth destination does not to exceed the unit transportation cost between the ith origin and jth destination.

The interpretation of dual constraints as the aim that origin-destination difference in price does not exceed transport price is equivalent to the principle of equilibrium with a sound economic meaning. Moreover, one can interpret the dual objective as the aim of a shipper to maximize the profit when purchasing at origin and selling at destination.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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