In this lab, students will build an interactive program in C++ that loads a graph, displays the adjacency matrix, and computes the shortest path between cities using Dijkstra’s algorithm. The program includes a menu for user interaction. By the end of this lab, students will be able to:
vector<vector<int>> adjacency matrix with 10 TN cities and distances.
vector<vector<int>> adjMatrix = {
{ 0, 35, 150, INF, INF, 40, INF, INF, INF, 80 },
{ 35, 0, 130, INF, 210, 20, 50, INF, INF, 70 },
{150, 130, 0, 80, 310, INF, INF, INF, INF, 90 },
{INF, INF, 80, 0, INF, INF, INF, 90, INF, 70 },
{INF, 210, 310, INF, 0, 190, 230, INF, 85, INF },
{ 40, 20, INF, INF, 190, 0, 60, INF, INF, INF },
{INF, 50, INF, INF, 230, 60, 0, INF, 140, INF },
{INF, INF, INF, 90, INF, INF, INF, 0, INF, INF },
{INF, INF, INF, INF, 85, INF, 140, INF, 0, INF },
{ 80, 70, 90, 70, INF, INF, INF, INF, INF, 0 }
};
INT_MAX to represent INF (no direct connection).
const int INF = INT_MAX;
vector<string> of city names matching matrix rows/columns.
vector<string> cityNames = {
"Murfreesboro", "Nashville", "Chattanooga", "Knoxville", "Memphis",
"Franklin", "Clarksville", "Johnson", "Jackson", "Cookeville"
};
unordered_map<string, int> to convert city names (case-insensitive) to matrix indices.
unordered_map<string, int> cityToIndex;
for (int i = 0; i < cityNames.size(); ++i) {
string lowercase = cityNames[i];
transform(lowercase.begin(), lowercase.end(), lowercase.begin(), ::tolower);
cityToIndex[lowercase] = i;
}
do...while loop that shows the following menu until the user chooses to exit:
===== TN Shortest Path Finder =====
1. Display Adjacency Matrix
2. Find Shortest Path (Dijkstra)
3. Exit
switch to handle the user’s choice.
void displayAdjacencyMatrix(const vector>& A, const vector& cityNames);
dijkstra() function to compute shortest distances and reconstruct the path.Murfreesboro → Franklin → Memphis) and the total distance.
// Function to compute the shortest path from a starting city to an ending city
void dijkstra(const vector<vector<int>> &A, int start, int end, const vector<string>& cityNames) {
int n = A.size(); // Number of cities (nodes)
// d[i]: shortest known distance from start to city i (initialized to INF)
// s[i]: predecessor of city i in the shortest path
// visited[i]: whether city i has been visited
vector<int> d(n, INF);
vector<int> s(n, -1);
vector<bool> visited(n, false);
// Distance to start city is 0
d[start] = 0;
// Main loop of the algorithm: repeat up to n times
// Please convert the following pseudocode into equivalent C++ code:
For step from 0 to n - 1:
// Initialize variable p to track the next closest unvisited node
p ← -1
// Find the unvisited node with the smallest tentative distance
For i from 0 to n - 1:
If node i is not visited AND (p is -1 OR d[i] < d[p]):
p ← i // Select node i as the current closest unvisited node
// If no such node exists or remaining nodes are unreachable, stop the algorithm
If p is -1 OR d[p] is INF:
Break // No more reachable nodes to process
// Mark the selected node p as visited
Mark p as visited
// Check all neighbors of node p
For v from 0 to n - 1:
// If there's a connection from p to v AND v has not been visited
If there is an edge from p to v AND v is not visited:
// If going through p offers a shorter path to v
If d[p] + A[p][v] < d[v]:
d[v] ← d[p] + A[p][v] // Update the shortest distance to v
s[v] ← p // Update the predecessor of v to p
// Reconstruct the shortest path from end to start using predecessors
vector<int> path;
for (int v = end; v != -1; v = s[v]) {
path.insert(path.begin(), v);
}
// Display the shortest path with city names
cout << "\nShortest path: ";
for (size_t i = 0; i < path.size(); ++i) {
cout << cityNames[path[i]];
if (i < path.size() - 1) cout << " → ";
}
cout << "\nTotal distance: " << d[end] << " miles\n";
}
===== TN Shortest Path Finder =====
1. Display Adjacency Matrix
2. Find Shortest Path (Dijkstra)
3. Exit
Enter your choice (1-3): 1
Adjacency Matrix (Distances in miles):
Murfreesboro Nashville Chattanooga Knoxville Memphis Franklin Clarksville Johnson Jackson Cookeville
Murfreesboro 0 35 150 INF INF 40 INF INF INF 80
Nashville 35 0 130 INF 210 20 50 INF INF 70
Chattanooga 150 130 0 80 310 INF INF INF INF 90
Knoxville INF INF 80 0 INF INF INF 90 INF 70
Memphis INF 210 310 INF 0 190 230 INF 85 INF
Franklin 40 20 INF INF 190 0 60 INF INF INF
Clarksville INF 50 INF INF 230 60 0 INF 140 INF
Johnson INF INF INF 90 INF INF INF 0 INF INF
Jackson INF INF INF INF 85 INF 140 INF 0 INF
Cookeville 80 70 90 70 INF INF INF INF INF 0
===== TN Shortest Path Finder =====
1. Display Adjacency Matrix
2. Find Shortest Path (Dijkstra)
3. Exit
Enter your choice (1-3): 2
Enter starting city: Murfreesboro
Enter ending city: Memphis
Shortest path: Murfreesboro → Franklin → Memphis
Total distance: 230 miles
===== TN Shortest Path Finder =====
1. Display Adjacency Matrix
2. Find Shortest Path (Dijkstra)
3. Exit
Enter your choice (1-3): 2
Enter starting city: Nashville
Enter ending city: Boston
Error: "Boston" is not found in the graph.
===== TN Shortest Path Finder =====
1. Display Adjacency Matrix
2. Find Shortest Path (Dijkstra)
3. Exit
Enter your choice (1-3): 3
Exiting program. Goodbye!
| Category | Criteria | Points |
|---|---|---|
| Graph Setup (10 points) |
The adjacency matrix and city list are properly defined | 10 |
| Menu Loop (15 points) |
Menu is functional with input handling | 15 |
| Dijkstra’s Algorithm (30 points) |
Correct and complete algorithm logic | 30 |
| Path Output (10 points) |
Displays correct path and distance | 10 |
| Error Handling (10 points) |
Handles invalid inputs gracefully | 10 |
| Main Function Implementation (10 points) |
All functions are correctly invoked in the main function | 10 |
| Code Readability & Comments (7 points) |
Maintain consistent indentation and spacing throughout the code. | 2 |
| Include comments that explain the purpose of key sections and logic. | 5 | |
| Test Cases & Output Accuracy (5 points) |
The output for different test cases is correct and consistent. | 5 |
| AI disclaimer (3 points) |
Please put an AI disclaimer at the top of your source code as comments. | 3 |
| Errors |
Your program has syntax errors, compiling errors, running errors, or infinite loops. | -50 points |
/*
Author: Your Name
Date: Month/Day/Year
Lab Purpose:
A.I. Disclaimer: please put your A.I. disclaimer here
*/
Please submit your Lab 5 source code file: lab5.cpp in D2L!