Assignment 5
Due: 2:00 PM on Monday, December 5, 2005
Question 1
The following problem has recent arisen at Bob's Dodgy Sales Company (a
division of Bob's Trucking Company): For years, Bob has had a team of
traveling salesman, each of whom has a specified set of cities that
they visit in a particular order. In the past, these salesman have
travelled by car. However, due to recent increases in both cash flow
and the number of police roadblocks, Bob has now decided that all
salesman will in future
travel by airplane. Each airline has a flight-route map specifying
which pairs of cities are linked by flights and the cost of a seat
on each city-to-city flight. Given an airline and a salesman route-list,
Bob would like to know how cheaply each salesman can follow his or her
traditional route; moreover, as each flight exposes a salesman to a
certain amount of cosmic radiation, Bob would also like to know
the number of flights these cheapest routes will involve (so he can
arrange life insurance coverage accordingly).
Write and document a Java program that solves the problem
described above -- that is, given an adjacency-matrix
description of a directed edge-weighted graph and a set of vertex
sequences on this graph, compute and display for each sequence (1) the
summed shortest paths (by summed edge-weight) of the adjacent
vertex-pairs in that sequence and (2) the summed shortest path
edge-counts of the adjacent vertex-pairs in that sequence.
A graph on n vertices is specified as an
(n + 1)-line file, where the first line has a single number
giving the value of n and the remaining n lines
specify an edge-weighted adjacency-matrix such that M[x,y] = z
for some positive non-zero integer z means that there is
an arc of weight z from x to y and
M[x,y] = * means that there is no arc from x to y.
For example, the directed edge-weighted graph
is described by file net1.dat, e.g.,
5
1: 0 50 * * 100
2: * 0 75 100 *
3: 200 * 0 50 *
4: 300 * 50 0 250
5: * * * * 0
A vertex-sequence file with n vertex-sequences is specified
by an (n + 1)-line file, where the first line specifies the
number of vertex-sequences and each of the remaining lines contains
a vertex-sequence consisting of some set of positive non-zero
integers separated by blanks. One such file relative to the graph
above is file route1.dat, e.g.,
10
2 1
1 4
4 2
2 5
3 5
5 2
2 1 4 2
4 2 1 4
4 2 5 1
2 5 1 4
You may assume that all input files are formatted correctly. Examples of
several program runs relative to the graph files
net1.dat and net2.dat
and the vertex-sequence file route1.dat
are given in script file out.script.
Hints
Questions 2 -- 3
The text of these questions is available in
PostScript and PDF
format. As re-drawing the graphs in Question #2 can become tedious, you
have been provided with template-diagrams for these questions in
PostScript and PDF
format that you can print off, fill in, and hand in with your
assignment.
Assignment Submission
Please hand in printed copies of all of your Java source code
files for Question #1 along with your answers for Questions #2 -- 3.
You must also submit the files for Question #1 electronically using
the submit-assignment command.
Note that each
such file must have the following comment block
at the top, where
the X's are replaced with the appropriate information. For instance,
my code for this assignment would begin with the following comment
block:
/////////////////////////////////////////////////////////////////
// CS 3711 (Fall 2005), Assignment #5, Question #1 //
// Program File Name: NRC.java //
// Student Name: Todd Wareham //
// Login Name: harold //
// MUN #: 8008765 //
/////////////////////////////////////////////////////////////////
You do not have to develop your code on our CS departmental systems.
However, as your code will be compiled and tested on our CS departmental
systems as part of the assignment marking process,
you should ensure that your code compiles and runs correctly on at
least one of these systems.
- Nov 14, 11:55 am
Assignment #5 posted.
Created: November 14, 2005
Last Modified: November 14, 2005
