Prim’s Algorithm in Telecommunication Cable Network Design — Minimum-Cost Wiring

Introduction

Telecommunication networks connect different locations such as towers, offices, exchanges, and data centres. These locations need to be connected using cables or other communication links.

Figure 1: Telecommunication network showing the locations and possible connections.

There are several ways to connect the locations, and each connection can have a different cost. Using every possible connection would increase the amount of cable required and may also increase the overall costs.

So the main problem is:

How can we connect all the required locations while keeping the total connection cost as low as possible?

We can look at this problem as a graph where each location is a vertex and each possible cable connection is an edge. The cost of a particular connection is the weight of that edge.

We can use Prim’s algorithm can solve this type of problem.

Prim’s algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) in a connected, weighted, undirected graph.

In this study I have considered a small telecommunication network and explained how Prim’s Algorithm can be used to find a minimum-cost connection structure.

Representing the Telecommunication Network as a Graph

For the example given below — six locations were considered:

Location — Description

A — Main Telecommunication Exchange
B — Tower 1
C — Tower 2
D — Tower 3
E — Regional Office
F — Data Center

Each location was represented by a vertex.

The possible cable connections are shown by edges. The number assigned to each connection represents its relative installation cost.

Figure 2: Telecommunication network graph showing the possible cable connections and their costs.

The connections are:

ConnectionCost
A – C → 3
B – C → 2
B – D → 5
C – D → 7
C – E → 6
D – E → 4
D – F → 3
E – F → 5

The values given above are only used to explain the algorithm. They are not actual cable installation prices.

What Is a Minimum Spanning Tree?

Before applying Prim’s Algorithm, it is useful to understand what a Minimum Spanning Tree is?

A Minimum Spanning Tree is a set of edges that:

1. Connects all vertices.
2. Does not contain a cycle.
3. Has the minimum possible total edge cost.

A spanning tree with V vertices contains V − 1 edges.

There are six locations in our example.

6 − 1 = 5 edges

Therefore, five connections are required to connect all six locations as a spanning tree.

For a cable network, this can be considered a basic low-cost connection plan. This doesn’t mean that a real telecom network would only use these five connections. Real networks normally need additional links for backup and reliability.

Figure 3: Minimum Spanning Tree obtained from the example telecommunication network, showing the selected connections and total cost of 17.

How Does Prim’s Algorithm Work?

Prim’s algorithm starts with one vertex and then slowly builds the spanning tree.

At each step it examines the connections from the locations that have already been selected. From these connections it selects the cheapest one that reaches a location that has not been selected yet.

The basic process is:

Start with one location → choose a cheap, valid connection → add the new location → repeat.

The connection must be valid because it should connect the existing tree to a new location. This also prevents the addition of cycles.

Applying Prim’s Algorithm to the Example

For this example, I will start from A, which represents the Main Telecommunication Exchange.The starting location can be different; however, A is used here for our calculation.

Step 1 — Start with A

Initially, only A was selected.

Selected locations: A

The available connections are as follows:

A — B = 4

A — C = 3

The smaller cost is 3, so we select:

A — C = 3

Total cost: 3

Selected locations: A, C

Step 2 — Select the Next Cheapest Connection

A and C have been selected.

We check their connections to locations that have not yet been selected.

The possible choices are as follows:

A — B = 4

C — B = 2

C — D = 7

C — E = 6

The smallest cost is 2.

So we select:

C — B = 2

The running total is:

3 + 2 = 5

Selected locations: A, B, C

Step 3 — Add D

The selected locations were A, B, and C.

The possible connections to an unselected location include the following:

B — D = 5

C — D = 7

C — E = 6

The cheapest option is:

B — D = 5

The running total becomes:

5 + 5 = 10

Selected locations: A, B, C, D

Step 4 — Add F

Now, A, B, C, and D are selected.

The remaining locations are E and F.

The available connections include:

C — E = 6

D — E = 4

D — F = 3

The cheapest connection is:

D — F = 3

The running total becomes:

10 + 3 = 13

Selected locations: A, B, C, D, F

Step 5 — Add the Last Location

Only E is left.

The possible connections to E are:

C — E = 6

D — E = 4

E — F = 5

The cheapest connection is:

D — E = 4

The final cost becomes:

13 + 4 = 17

All six locations have now been connected.

Figure 4: Step-by-step selection of edges using Prim’s Algorithm, resulting in a minimum total cost of 17.

Final Connection Sequence

Step 1: A → C, cost 3

↓

Step 2: C → B, cost 2

↓

Step 3: B → D, cost 5

↓

Step 4: D → F, cost 3

↓

Step 5: D → E, cost 4

At the bottom:

Final Minimum Cost = 17

Final Result

Step — Connection — Cost — Total Cost

1 — A — C — 3–3
2 — C — B — 2–5
3 — B — D — 5–10
4 — D — F — 3–13
5 — D — E — 4–17

Therefore:

Minimum Total Cost = 17 cost units

The selected connections are:

A — C = 3

C — B = 2

B — D = 5

D — F = 3

D — E = 4

There are six vertices and five selected edges, which is correct for a spanning tree.

Why Does Prim’s Algorithm Not Select Every Cheap Edge?

One aspect that can be confusing when learning Prim’s Algorithm is that it does not simply select the smallest edge in the entire graph.

For example, after selecting A — C and C — B, there is already a path between A and B.

If we select A — B, a cycle would be created.

A Minimum Spanning Tree cannot contain any cycles because adding a cycle would mean that one of the edges could be removed without disconnecting the graph.

Prim’s Algorithm searches for the cheapest edge that connects the current tree to a new location.

This is why the algorithm is different from simply arranging all the edges according to their cost and selecting them one by one.

Prim’s Algorithm in Simple Steps

1. Choose a starting vertex.
2. Mark the starting vertex as selected.
3. Find the cheapest edge from a selected vertex to an unselected vertex.
4. Add that edge to the MST.
5. Mark the new vertex as selected.
6. Repeat the same process until all vertices have been selected.
7. Once all the vertices are connected, the Minimum Spanning Tree is complete.

Pseudocode

Prim(G):
    Choose a starting vertex
    Mark the starting vertex as visited
    MST = empty set
    TotalCost = 0
    while not all vertices are visited:
        Find the minimum-weight edge
        connecting a visited vertex
        to an unvisited vertex
        Add the edge to MST
        Mark the new vertex as visited
        Add its cost to TotalCost
    return MST and TotalCost

Python Implementation

To understand the algorithm practically, I used a simple Python program with an adjacency matrix.

INF = 999999

graph = [
    [0, 4, 3, INF, INF, INF],
    [4, 0, 2, 5, INF, INF],
    [3, 2, 0, 7, 6, INF],
    [INF, 5, 7, 0, 4, 3],
    [INF, INF, 6, 4, 0, 5],
    [INF, INF, INF, 3, 5, 0]
]
vertices = len(graph)
selected = [False] * vertices
selected[0] = True
total_cost = 0
print("Selected Connections:")
for _ in range(vertices - 1):
    minimum = INF
    x = 0
    y = 0
    for i in range(vertices):
        if selected[i]:
            for j in range(vertices):
                if not selected[j] and graph[i][j] < minimum:
                    minimum = graph[i][j]
                    x = i
                    y = j
    print(chr(65 + x), "-", chr(65 + y), ":", minimum)
    total_cost += minimum
    selected[y] = True
print("Minimum Total Cost:", total_cost)

Program Output

Selected Connections:
A - C : 3
C - B : 2
B - D : 5
D - F : 3
D - E : 4
Minimum Total Cost: 17

The output matches the result obtained from the manual calculation.

Understanding the Code

The graph is stored in the form of a matrix.

Get Shriya Biju’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The first row represents the connections from A:

[0, 4, 3, INF, INF, INF]

This means:

A to A = 0

A to B = 4

A to C = 3

A to D = no direct connection

A to E = no direct connection

A to F = no direct connection

Here, INF represents a connection that is not available in our example.

The following line creates the selected array:

selected = [False] * vertices

Initially, all locations are unselected.

Then:

selected[0] = True

selects A because A is represented by index 0.

The nested loops search for the smallest edge that connects a selected location to an unselected location.

After finding the edge, its cost is added to total_cost and the new location is marked as selected.

The loop runs vertices − 1 times because a spanning tree containing six vertices has five edges.

Time Complexity

The time taken by Prim’s Algorithm depends on how it is implemented.

Let:

V = number of vertices or locations

E = number of edges or possible connections

Using an Adjacency Matrix

The Python program above uses an adjacency matrix.

Its time complexity is:

O(V²)

This approach is simple and works well for learning the algorithm and for small or dense graphs.

Using a Priority Queue

Prim’s Algorithm can also be implemented using an adjacency list and a priority queue or min-heap.

A commonly used complexity for this approach is:

O(E log V)

This can be useful for sparse graphs where the number of actual connections is much smaller than the number of possible connections.

A Small Complexity Example

Suppose a network has 1,000 telecommunication towers.

With an adjacency matrix, the work is proportional to V².

Therefore:

1,00⁰² = 1,000,000

matrix positions are involved in the repeated scanning process.

That doesn’t mean that there are one million actual cable connections. It represents the size of the matrix being processed.

For a larger and sparse network, an adjacency list with a priority queue can be more suitable.

Advantages of Prim’s Algorithm

1. Reduces the Total Connection Cost

The main purpose of using Prim’s Algorithm in this example is to find a Minimum Spanning Tree with the minimum total edge cost.

For our network, the final cost is 17 units.

2. Connects All Locations

If the graph is connected, the resulting spanning tree connects every vertex.

3. Avoids Cycles

The algorithm connects the current tree to a new unselected vertex, which helps ensure that the resulting spanning tree does not contain any cycles.

4. Useful for Network Problems

The same idea can be used in different situations where several locations need to be connected while considering connection costs.

5. Easy to Understand

The basic process of choosing a suitable low-cost connection at every step makes the algorithm relatively easy to understand and implement.

Limitations

Prim’s Algorithm is useful for finding a minimum-cost spanning tree, but a real telecommunication network has many other requirements.

1. Cost Is Not the Only Factor

A real network may also need to consider:

• Bandwidth
• Reliability
• Latency
• Maintenance
• Installation time
• Geographical conditions
• Permissions
• Future expansion

Prim’s Algorithm alone does not take all of these factors into account.

2. No Automatic Backup Connections

A Minimum Spanning Tree does not contain cycles.

This is useful when unnecessary connections need to be avoided, but it can be a problem in a real communication network.

If one cable fails, there may not be another route between two locations.

Real telecom networks may therefore need additional links for redundancy.

3. Depends on the Given Costs

The result depends on the weights assigned to the edges.

If the estimated installation costs are not accurate, the resulting network may not be suitable for the actual situation.

4. The Graph Must Be Connected

A single Minimum Spanning Tree can be created only when all the required vertices are connected through available edges.

If a location has no path to the rest of the network, one spanning tree cannot connect all the locations.

Where Can This Idea Be Used?

Fiber-Optic Networks

A telecom provider can use a similar graph model when planning connections between buildings, exchanges, and other facilities.

Mobile Towers

Mobile towers can be represented as vertices, while possible backhaul connections can be represented as weighted edges.

Data Centers

Data centers and other network facilities can be represented as nodes, with possible physical connections having different costs.

Campus Networks

A university campus may have several buildings that need to be connected through physical communication cables.

Rural Connectivity

When locations are spread over a large area, a cost-based network plan can help create an initial connection structure.

Prim’s Algorithm and Real Telecommunication Networks

There is an important difference between this example and an actual telecom project.

Prim’s Algorithm mainly answers one question:

What is the minimum total edge cost needed to connect all the locations in this graph?

A real network designer has to consider many other things as well.

For example:

• What happens if a cable gets damaged?
• Is there enough bandwidth?
• Is the proposed route physically possible?
• Is the terrain suitable?
• Are permissions required?
• How much maintenance will the network need?
• Will the network support future users?
• Is backup connectivity necessary?

Because of these factors, a Minimum Spanning Tree should not be treated as the complete design of a real telecommunication network.

It is better to consider it as a starting point for finding a low-cost connection structure. Other requirements can then be considered according to the actual project.

Figure 5: Network connections selected using Prim’s Algorithm to form the Minimum Spanning Tree.

What the Example Shows?

The example started with six locations and nine possible connections.

After applying Prim’s Algorithm, five connections were selected:

Selected Edge — Cost

A — C — 3
C — B — 2
B — D — 5
D — F — 3
D — E — 4

Adding the values gives:

3 + 2 + 5 + 3 + 4 = 17

Therefore, the final Minimum Spanning Tree has a total cost of:

17 cost units

The number of selected edges is also correct:

6 − 1 = 5

This provides a simple check that the final result forms a spanning tree.

Key Takeaways

• A telecommunication network can be represented as a weighted graph.
• Network locations can be represented as vertices.
• Cable connections can be represented as edges.
• Cable installation costs can be represented as edge weights.
• Prim’s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree.
• An MST connects all vertices without creating cycles.
• An MST contains V − 1 edges.
• In this example, six locations required five selected connections.
• The minimum total cost obtained was 17 cost units.
• The adjacency-matrix implementation has O(V²) time complexity.
• A priority-queue implementation can commonly achieve O(E log V) complexity.
• Real telecommunication networks may also require redundancy, reliability, bandwidth, and scalability.

Conclusion

Telecommunication network design involves connecting several locations while keeping infrastructure costs under control.

When the problem can be represented as a connected, weighted, undirected graph, Prim’s Algorithm provides a systematic way to find a Minimum Spanning Tree.

In this example, six locations were connected using five cable connections with a total cost of 17 units.

The algorithm selected the cheapest valid connection at each step while avoiding cycles and making sure that every location became part of the network.

However, minimum cost alone is not enough for a complete telecommunication network. Practical networks may also require redundancy, reliability, bandwidth, geographical feasibility, maintenance, and future expansion.

Therefore, Prim’s Algorithm shall be used as a starting point for finding a low-cost network structure. Other engineering requirements can then be considered when designing the actual network.

References

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press.
2. GeeksforGeeks, Prim’s Minimum Spanning Tree (MST) — Greedy Algorithm.
3. Programiz, Prim’s Algorithm.
4. TutorialsPoint, Prim’s Algorithm.
5. Course notes and lecture material on Design and Analysis of Algorithms.