- Introduction
Navigation devices utilising Global Positioning System (GPS) satellite technology have
become commonplace in today’s society. Road networks can be modelled and information
about the distances between locations are included so that choices can be made by the users
of GPS about their choice of route between two locations based on the shortest distance.
Road networks are modelled utilising Graph Theory. Locations are used as the vertices in the
graph while the roads between locations are used as the edges of the graph. The edges are
given weights based on the distance of the road section between two locations.
The government plans on building a road network between a set of locations and want to
investigate the shortest distances and routes from the government’s capital to all other
locations in the land. Locations have been mapped with Cartesian co-ordinates i.e. x,y coordinates,
and the roads are to be built as straight lines between the various locations.
Due to various geographic features some road segments between locations cannot be built or
the cost of doing so would be prohibitive. The underlying graph that models the road
network is, therefore, not complete1.
For a set of locations and possible road segments which have been randomly generated (see
Task 1 below), you are to store the location and segment data in a graph (see Task 2 below).
You will then investigate the distance and route of the shortest path from the government’s
capital to all other locations based on:
1. the graph which includes all of the given the road segments that make up the road
network (see Task 3 below)
2. the graph which includes only those segments included in the minimum cost set of
road segments which connects all vertices (see Tasks 4 and 5 below)
