Shortest Paths in a Network
Introduction
Below is a java applet that can be used to find shortest paths in a network.
Press the Go Wandering button to see the applet.
The applet has two mouse modes: Build Network and Edit Travel
Times.
Build Network
In Build Network mode, the mouse can be used to build a
network.
To do this,
you specify arcs in the network by a pair of mouse clicks.
The first mouse click must be on an existing node in the network.
The second mouse click can be anywhere on the drawing canvas.
If it is on an existing node, then an arc is created connecting the two
selected nodes. By default, the direction of the arc is from the first node to
the second node. To reverse the direction, simply hold the shift
key while making the second click.
If the second mouse click is not on any existing node, then a new node is
automatically created at the clicked location and an arc is created as
before.
The applet always initializes the network with one preexisting node, which
is labeled a. We refer to this node as the root node. It
plays a special role in the following discussion.
By forcing you to build the network arc by arc always using an existing node
for the first click, we guarantee that the network will be connected. Also, we
use those arcs which involved the creation of a new node as the
tree arcs for an initial spanning tree.
All other arcs are non-tree arcs. Tree arcs are shown in red.
Edit Travel Times
After defining the nodes and arcs, you need to specify
traversal times for the arcs.
Choosing the Edit Travel Times mode with the choice box, you can
edit these values one at a time.
The values are initially set to zero
and are now shown. To change a travel time for a specific arc, click on
the arc. A textfield will appear in which you can enter a value and then set
it by clicking on the Set Time button.
Note that the root node's supply is automatically set
so that the total supply equals the total demand. Hence, there is no need ever
to edit the supply at the root node. In this way the applet ensures that none
of the problems are trivially infeasible in the sense of a misbalance between
total supply and total demand.
Randomly Generating Problems
As an alternative to generating problems by hand, you can click on
Generate Random Problem in either of the above two mouse modes
to quickly produce a random network with random travel times.
The textfield labeled Nodes can be editted to specify
the number of nodes in the network (the window can be resized as desired
to accomodate larger networks). If the Seed field is left blank
then an internally generated seed value will be used and the behavior of the
random problem generator will be different every time the applet is run.
If,
however, a seed value is given (it must be an integer), then that value is
used to seed the random number generator.
Specifying a value for the number of
nodes and for the seed uniquely determines the sequence of problems
generated.