Activity based

Project Report on
Discrete Mathematics
Submitted to Vishwakarma University, Pune
Under the Initiative of
Contemporary Curriculum, Pedagogy, and Practice (C2P2)

By
Student Name: Raj Balu Patil
SRN No: 31240370
Roll No: 129
Div: F
Second Year of Engineering

Department of Computer Engineering

Faculty of Science and Technology

Academic Year
2024-2025
 Discrete Mathematics – P2

Designing a Park with Minimum Cost Pathways Using Prim's

Algorithm

Designing a Park with Minimum Cost Pathways Using Prim's Algorithm

Project Statement:

To design a park with multiple sections connected by pathways of varying costs, represented as a weighted
graph where nodes are sections, and edges represent pathways with associated costs. Use Prim's Algorithm
to calculate the minimum cost of connecting all sections with pathways, ensuring that each section is
reachable.

Problem Description:

The goal of this project is to design a park layout that includes several distinct
sections, each connected by pathways with specific costs. To ensure all sections of
the park are accessible, we need to determine the minimum cost network of
pathways using Prim's Algorithm. This algorithm will help find the minimum
spanning tree of the graph, minimizing the overall pathway costs while connecting
all park sections.
The solution will involve representing the park as a graph where:
- Each section is a node.
- Each pathway is an edge with an associated cost.
Using Prim's Algorithm, we will connect all sections with the minimum total cost for
pathways, making sure that each section is accessible from any other section.

Page |2
 Discrete Mathematics – P2

Chapter No 3
Implementation of Prim's Algorithm for Park Design

To design a park with multiple sections connected by pathways with various costs,
we represent the park layout as a weighted graph. In this graph:

 Nodes represent different sections of the park.

 Edges represent pathways between sections, with each edge assigned a specific
cost.

Prim's Algorithm helps determine the minimum cost to connect all park sections with
pathways. The goal is to build a minimum spanning tree (MST), which ensures each
section is accessible with the least possible total cost for pathways.

Algorithm for Prim's Algorithm:

1. Initialize: Start with any arbitrary section of the park, marking it as visited.
2. Select Minimum Edge: From the visited nodes, find the edge with the lowest
cost that connects to an unvisited node.
3. Add Edge to MST: Add this edge to the MST and mark the connected node as
visited.
4. Repeat: Continue the process, each time selecting the minimum-cost edge
from visited to unvisited nodes, until all nodes are part of the MST.
5. Result: The MST now represents the minimum-cost pathway network that
connects all sections of the park.

This approach ensures the minimum cost required to connect all sections without
creating any cycles in the graph.

Flow Chart:

1. Start
2. Select Initial Node → Mark as visited
3. Check All Edges to Unvisited Nodes Identify the minimum-cost edge
connecting the visited node(s) to any unvisited node.
4. Add Edge and Node to Visited Set
5. Repeat Until All Nodes Are Visited
6. End

Page |3
 Discrete Mathematics – P2

Python Code Implementation

Here's the code for implementing Prim's Algorithm. This code assumes you have a graph
represented as an adjacency list, where each section of the park is a node and each pathway between
sections has an associated cost.

import heapq

# Define the graph as an adjacency list

# Each key is a node, and its value is a list of tuples (cost, neighboring_node)

graph = {

'A': [(1, 'B'), (4, 'C')],

'B': [(1, 'A'), (2, 'C'), (5, 'D')],

'C': [(4, 'A'), (2, 'B'), (3, 'D')],

'D': [(5, 'B'), (3, 'C')]

def prims_algorithm(graph, start_node):

# Initialize visited nodes set

visited = set([start_node])

# Priority queue to store edges with their costs, starting from start_node

edges = [(cost, start_node, neighbor) for cost, neighbor in graph[start_node]]

[Link](edges)

# Minimum cost to connect all sections and list of edges in the MST

total_cost = 0

mst_edges = []

while edges:

# Choose the edge with the minimum cost

cost, from_node, to_node = [Link](edges)

Page |4
 Discrete Mathematics – P2

if to_node not in visited:

# Add this edge to the MST

[Link](to_node)

total_cost += cost

mst_edges.append((from_node, to_node, cost))

# Add all edges from the newly added node to the priority queue

for next_cost, next_node in graph[to_node]:

if next_node not in visited:

[Link](edges, (next_cost, to_node, next_node))

return total_cost, mst_edges

# Run Prim's Algorithm from an arbitrary start node, e.g., 'A'

start_section = 'A'

min_cost, mst = prims_algorithm(graph, start_section)

print(f"Minimum Cost to Connect All Sections: {min_cost}")

print("Edges in Minimum Spanning Tree:")

for edge in mst:

print(f"{edge[0]} - {edge[1]} with cost {edge[2]}")

output:-

Page |5
 Discrete Mathematics – P2

Chapter No 4
Ideas to Use the Concept in Future? (Future Scope or Applications )

Future Applications of Prim's Algorithm and Minimum Spanning Tree (MST)

Concepts

The concept of minimum spanning trees, as demonstrated by using Prim’s Algorithm

in the park design project, has significant applications in various fields. Here are
potential areas where MST concepts can be applied:

1. Urban and Transportation Planning

In urban areas, MST algorithms help in designing cost-effective road networks,
ensuring that different city sections are interconnected at the lowest possible
infrastructure cost. This approach is beneficial in expanding cities where
optimizing connectivity while minimizing construction expenses is essential.
2. Power Grid Design
MSTs are valuable in designing electrical grids where power stations need to
be connected to multiple regions. By minimizing the pathway cost, energy
providers can deliver electricity to each part of a city or region efficiently
without redundancy, reducing costs and power losses.
3. Computer Networks
In computer networking, MSTs optimize the layout of local area networks
(LANs). By connecting devices (computers, printers, etc.) with the minimum
amount of cabling, MSTs reduce setup costs while maintaining connectivity,
especially important in large office spaces or campus environments.
4. Pipeline Distribution Systems
Pipeline networks for distributing resources like water, gas, or oil often require connection
points at various locations. MST algorithms minimize the length and cost of these pipelines,
ensuring efficient resource distribution with minimum infrastructure.
5. Telecommunications Networks
For designing telecommunications infrastructure like fiber optic or cable networks, MSTs
ensure that the infrastructure covers all necessary areas with minimal cost. This results in
reduced installation costs for reaching different areas, especially in rural regions.

Page |6
 Discrete Mathematics – P2

Conclusion

In this project, we successfully applied Prim’s Algorithm to design a cost-effective park layout
where all sections are connected with minimal pathway expenses. Representing the park as a
weighted graph allowed us to effectively apply the principles of discrete mathematics, using a
minimum spanning tree (MST) to ensure accessibility across all sections of the park at the lowest
possible cost.

Prim’s Algorithm provided an efficient solution by incrementally adding the least costly pathways,
thereby minimizing the total cost of connecting all park sections without creating any redundant
connections. This project demonstrates the practical value of MSTs in various applications, from
urban planning to network design, where cost-efficiency and complete connectivity are essential.

Page |7