Shortest Paths Problem

Mouse's Mode:     (Seed: , Nodes: )    



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 is where we are going.

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.

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. 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.

Click here for the original class project desription (Java version).

Finally, click here for the Java Applet version of the same tool.