Project 4 C++ implementation to find shortest path

1
ECE250: Lab Project 4

1. Project Description
The goal of this project is to write a C++ implementation to find shortest path in a graph using
Dijktsra’s algorithm. Using your implementation, a user can find the shortest path
between two given cities using an undirected graph.
We ask you to write a C++ class undirectedGraph, representing cities (as nodes) and roads
(as edges) connecting these cities. This is a weighted graph in which each edge represents the
corresponding distance (as a double data type) between two cities. You have to write your own
implementation of the undirected graph. It is not allowed to use the C++ Standard Library to
implement your data structures.
2. Program Design
Write a short description of your design. You will submit this document along with your C++
solution files for marking. This document must include your design decisions. Please refer to
the course website for “Programming Guidelines” and the expected content for your design
document.
3. Project Requirements
Write a test program (named undirectedGraphtest.cpp) that reads commands from
standard input and writes the output to standard output. The program will respond to the
commands described in this section.
Command Parameters Description Output
i name Inserts a node (city) to a
graph.
success: if the insertion
command was successful
failure: if the insertion
command was unable to
complete since the city was
already in the graph.
setd name1;name2;d Assigns a distance (d) to
the edge (road) connecting
two cities (name1 and
name2).
success: if the command was
able to assign the distance to the
connection or to update an
existing distance between two
cities successfully.
failure: if the command was
unable to complete because both
cities or one of them do(es) not
exist.
s name Searches for a city with the
specified name.
found name
not found
2
Command Parameters Description Output
degree name Prints the degree of the
city (name).
degree of name value
graph_nodes Returns the number of
nodes (cities) in the graph.
number of nodes value
graph_edges Returns the number of
edges (roads) in the graph.
number of edges value
d name1;name2 Prints the distance
between two cities (name1
and name2).
Note: Two cities (name1
and name2) are adjacent.
direct distance name1 to
name2 value
failure: if one or both nodes
(cities) are not found, or two
nodes are not directly connected.
shortest_d name1;name2 Finds the shortest distance
between two cities (name1
and name2).
shortest distance name1 to
name2 value
failure: if one or both cities are
not found or cities are not
reachable from each other.
print_path name1;name2 Prints the path between
two cities (name1 and
name2) such that the sum
of the distances of its
constituent edges (roads)
is minimized (shortest
path).
name1 … name2
failure: if one or both cities are
not found or two cities are not
reachable from each other.
clear
Deletes all the nodes and
edges from the graph.
success
Provide an analysis for the time complexity of your implementation of Dijkstra’s algorithm.
• Test Files
The course website contains example input files for the corresponding output files. The files
are named test01.in, test02.in and so on with the output files named test01.out, test02.out
and so on. 
3
4. How to Submit Your Program
Once you have completed your solution and tested it comprehensively in your computer or on
the lab computers, you have to transfer your files to the eceUbuntu server and test there since
we perform the automated testing using this environment. Once you finish testing in the
eceUbuntu server, you will create a compressed file (tar.gz) that should contain:
• A typed document (maximum two pages) describing your design. Submit this
document is PDF format (e.g., design.pdf).
• A test program (undirectedGraphtest.cpp) that reads the commands and writes the
output.
• Required header files and classes (ending in .h .cpp).
• If your implementation requires more than one file listed in g++ line for compilation,
you have to add to your design document the complete g++ command line and also
provide a make file (named Makefile).
The name of your compressed file should be xxxxxxxx_pn.tar.gz, where xxxxxxxx is your
UW user id (e.g., jsmith) and n is the project number that is 4 (four) for this submission.