Travel to SLCC’s Campuses Below is a map of some of SLCC’s locations followed by the distances between campuses. Taylorsville to South City: 8 miles Taylorsville to West Valley: 6.3 miles Taylorsville to Herriman: 15.8 miles Taylorsville to Miller: 9.3 miles Taylorsville to Jordan: 9 miles Jordan to South City: 16 miles Jordan to West Valley: 10.5 miles Jordan to Miller: 5 miles South City to West Valley: 11.2 miles South City to Herriman: 24 miles South City to Miller: 12.3 miles Herriman to West Valley: 14 miles Herriman to Miller: 11 miles Miller to West Valley: 15 miles 2. (10 points) Apply the Nearest Neighbor Algorithm to your graph. Write your answer as a list of vertices, starting and ending at the Taylorsville Campus, and give the total miles. 3. (10 points) Apply the Sorted Edges Algorithm to the graph. Write your answer as a list of vertices, starting and ending at the Jordan Campus, and give the total miles. 4. (10 points) Find the minimum cost (lowest miles) spanning tree using Kruskal’s Algorithm. What is the total miles? Draw the graph. 5. (5 points) a. Given your answers above, if you had to travel to all six locations and return to where you started, which method would you use? Why? 1. (15 points) On a separate paper draw and label a graph of the map (do not include Meadowbrook). The locations are the vertices – use T for Taylorsville, J for Jordan, S for South City, W for West Valley, M for Miller, and
for Herriman. The weights of the edges are the distances, in miles, between campuses. b. Even though Kruskal’s Algorithm produces the fewest total miles, why would you not use it if you had to return to where you started? Answer the questions on the next page:
The Correct Answer and Explanation is:
To answer these questions, let’s break them down one by one:
2. Nearest Neighbor Algorithm (Starting and Ending at Taylorsville)
The Nearest Neighbor Algorithm involves starting at a chosen vertex (in this case, Taylorsville) and always traveling to the closest unvisited vertex until all vertices have been visited, then returning to the starting vertex. Here’s how it works:
- Start at Taylorsville.
- Taylorsville to West Valley (6.3 miles).
- West Valley to Miller (15 miles).
- Miller to Herriman (11 miles).
- Herriman to South City (24 miles).
- South City to Jordan (16 miles).
- Jordan to Taylorsville (9 miles).
Order of visits: Taylorsville → West Valley → Miller → Herriman → South City → Jordan → Taylorsville.
Now, let’s calculate the total miles:
- 6.3 (Taylorsville to West Valley)
- 15 (West Valley to Miller)
- 11 (Miller to Herriman)
- 24 (Herriman to South City)
- 16 (South City to Jordan)
- 9 (Jordan to Taylorsville)
Total Miles: 6.3 + 15 + 11 + 24 + 16 + 9 = 81.3 miles.
3. Sorted Edges Algorithm (Starting and Ending at Jordan)
In the Sorted Edges Algorithm, we first sort all the edges (distances between campuses) in ascending order, then choose the shortest edges that don’t form a cycle, starting and ending at the Jordan campus.
Sorted edges (from shortest to longest):
- 5 miles: Jordan to Miller
- 6.3 miles: Taylorsville to West Valley
- 9 miles: Taylorsville to Jordan
- 9.3 miles: Taylorsville to Miller
- 10.5 miles: Jordan to West Valley
- 11 miles: Herriman to Miller
- 11.2 miles: South City to West Valley
- 12.3 miles: South City to Miller
- 15 miles: Miller to West Valley
- 15.8 miles: Taylorsville to Herriman
- 16 miles: Jordan to South City
- 24 miles: South City to Herriman
Starting at Jordan, we connect the edges in increasing order of distance, avoiding any cycles:
- Jordan to Miller (5 miles)
- Miller to West Valley (15 miles)
- West Valley to Taylorsville (6.3 miles)
- Taylorsville to South City (8 miles)
- South City to Herriman (24 miles)
- Herriman to Jordan (16 miles)
Total Miles: 5 + 15 + 6.3 + 8 + 24 + 16 = 74.3 miles.
4. Minimum Spanning Tree (Using Kruskal’s Algorithm)
Kruskal’s algorithm finds the minimum spanning tree, which is a tree connecting all vertices with the minimum total weight (distance in this case) without any cycles. It works by sorting all edges and adding them one by one, as long as they don’t form a cycle.
Sorted edges (ascending order):
- 5 miles: Jordan to Miller
- 6.3 miles: Taylorsville to West Valley
- 9 miles: Taylorsville to Jordan
- 9.3 miles: Taylorsville to Miller
- 10.5 miles: Jordan to West Valley
- 11 miles: Herriman to Miller
- 11.2 miles: South City to West Valley
- 12.3 miles: South City to Miller
- 15 miles: Miller to West Valley
- 15.8 miles: Taylorsville to Herriman
- 16 miles: Jordan to South City
- 24 miles: South City to Herriman
Now, using Kruskal’s algorithm, we select edges in order until all campuses are connected (ensuring no cycles):
- Jordan to Miller (5 miles)
- Taylorsville to West Valley (6.3 miles)
- Taylorsville to Jordan (9 miles)
- Taylorsville to Miller (9.3 miles)
- South City to West Valley (11.2 miles)
- South City to Miller (12.3 miles)
Now, we’ve connected all campuses, and the total cost is:
Total Miles: 5 + 6.3 + 9 + 9.3 + 11.2 + 12.3 = 53.1 miles.
5. a. Which Method to Use?
If you had to visit all six locations and return to your starting point, the best method would be the Nearest Neighbor Algorithm. While it doesn’t guarantee the absolute minimum total distance (it’s more of a heuristic), it does give you a practical and efficient route. The total distance of 81.3 miles is reasonable compared to the Sorted Edges Algorithm’s 74.3 miles, but the Nearest Neighbor Algorithm’s route is more flexible and easier to follow in real-world conditions. The Sorted Edges Algorithm is useful for minimizing the cost of the edges but doesn’t focus on starting and ending at specific points.
5. b. Why Not Use Kruskal’s Algorithm?
Kruskal’s Algorithm gives the minimum spanning tree (MST), which minimizes the total distance but does not form a complete cycle. The MST is not useful for a trip that requires returning to the starting point. Kruskal’s algorithm focuses on connecting all locations with the least total distance but does not consider the requirement to visit all locations and return to the starting point. To achieve that, you would need a solution like the Traveling Salesman Problem (TSP), which finds the shortest cycle, or use a method like Nearest Neighbor or Sorted Edges.
