CSE 247 Module 6: Shortest Paths
Extension 1: ( points):
[an error occurred while processing this directive]
Abstract: We have seen Dijkstra's shortest path algorithm earlier in this course. Prim's Algorithm
is similar to Dijkstra's and is used to find the minimum spanning tree of a graph.
Prim's Minimum Spanning Tree Algorithm
Author: Yonatan David and Tim Heyer
In this assignment, you will apply Prim's algorithm and the concept of a minimum spanning tree to a real-world network optimization problem.
Note: Prim's Algorithm is discussed in detail in Section 23.2 (pg. 634) of the text.
A spanning tree is a tree derived from an edge-weight graph that touches each vertex of the graph exactly once.
The fundamental property of a minimum spanning tree (MST) is that the sum of the weights of its edges is no larger than the weight of any other
As such, the tree will contain all vertices of its corresponding graph, and must visit each vertex in a specific order.
The minimum spanning tree of a graph is one that is:
- inclusive of all vertices
- the minimum total weighting for its edges
Minimum spanning trees have a variety of real-world applications. For example, we use minimum spanning trees to model:
Instead of trying to find the shortest path from one point to another like Dijkstra's algorithm, Prim's algorithm calculates the minimum spanning tree
of the graph. We start at one vertex and select an edge with the smallest value of all the currently reachable edge weights.
Algorithms that operate like this—in that they always make the locally optimal choice—are known as
greedy algorithms. Your task is to compute the minimum distance,
as well as a mapping of the path taken, to visit all vertices using Prim's algorithm as described below.
- Given a start vertex, compare the weights of all reachable edges and choose the one with the least weight.
If there are multiple edges with the same weight, choose one of the edges.
- Visit the vertex to which the edge connects.
- Reevaluate all available edges, including previously visited vertices and their respective edges. Choose the edge
with the least weight that leads to an unvisited vertex.
- Repeat step 3 until all vertices have been visited.
As you visit new vertices, be sure to map the new vertex to the edge you took to reach it in the toEdge map.
This map will be used to calculate the total distance traveled and will become your minimum spanning tree.
For this assignment, you are an engineer working for a telecommunications firm. Your firm wants to introduce landline telephone service to a developing country and
has commissioned you for the task. A surveyor has prepared a layout of the cities (vertices) to which you must run telephone lines, as well as the available paths between each city (edges).
Due to geographic restrictions, some cities will have multiple paths to reach them and others may have only one.
Additionally, each of these paths has a different weight which is the cost of using a given path based on distance, geographic obstacles, and accessibility.
You are required to run a telephone line that connects each city in the country (graph) and to do so as efficiently as possible. In other words, minimize the total
amount of telephone line used.
Note that telephone service can travel to any city connected to the network you install. As such, every city does not need a wire to every other city; there only needs to be one
common wire which connects every city.
With the layout of the country in hand, you must now figure out how to connect every city while minimizing your firm's costs and therefore maximizing their profits.
You quickly identify that you'll need to construct a minimum spanning tree of the cities and their distances to determine along which paths you'll
need to install wire. Luckily, you're familiar with Prim's algorithm so you fire up Eclipse and begin writing a solution in your favorite programming language, Java.
- Update your repository as usual.
- In the prim.util package of the extensions source folder, notice that the graphing classes are similar to
those used in the Dijkstra's shortest path lab, but are slightly modified to use an undirected graph instead of the previously used directed graph.
Familiarizing yourself with these classes will make this assignment much easier.
- In the prim package, find and open the MinimumSpanningTree class.
- Complete the run() method using the steps of Prim's algorithm outlined above.
- Pass the unit tests (Note: the test can take up to a minute to finish running).
The unit tests work by constructing a graph with a preconfigured minimum spanning tree. While it is true that in general, graphs will often have
more than one MST (though all with the same total weight), the graph generated by the unit tests will have only one.
Therefore, by following all of the steps in Prim's algorithm you will find and return the same MST known to the test.
When you done with this extension, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
- If you request propagation, it does not happen immediately,
but should be posted in the next day or so
This demo box is for extension 6.1
End of extension 1