CS 341, Spring 2023

Individual Programming Project

Due: midnight – Saturday 12/02/23

Graph (Minimum Spanning Tree) – Laying Pipelines:

Oil has been found – in great quantities by Our Hush-Hush Inc. Where and how much of oil is discovered is not to be divulged. But we need to bring the product to market – efficiently and using least cost network of pipes. The source locations (up to 50) are named slyly – again for secrecy. The distances between these locations are known. The cost of interconnecting two locations is directly proportional to the distance between them. We have to develop a plan to interconnect these locations with minimum cost.

The input file – “blackgold.txt” – contains locations and distances between them.

Your application will load, and setup the graph from the input file. It should output the network of connections to be built with minimum length.

Example input file:

Blue Gold 500

Gold Red 300

Magenta Yellow 438

Blue Yellow 531

Magenta Blue 865

Red Purple 765

Blue Purple 387

Brown Magenta 1100

Brown Blue 435

Gold Silver 654

Gold Purple 186

Export your project by midnight of the due date.

BONUS:

Given two locations, find the best possible way to interconnect the locations given the distances between the locations.