My program contains 2 classes: Node and Network, and 2 functions: Main and readNodes.
Node Class
The Node class represents one node in the network, and has member variables
to represent its state,
eg: wether or not it is permanent, how many links it has, which nodes
it is linked to, etc.. All these variables are private.
It also has member functions to add a link, check for the existance
of a link, check wether its permanent or not, etc..
All the member functions are public.
Network Class
The network class represents a whole network. It is populated with
nodes.
It has member variables to hold the nodes, the number of nodes, and
the shortest path found so far.
They are all private.
It has member functions to add a node, get a node, check if a node
exists, and the most important of all:
get the shortest path between 2 nodes.
getShortestPath function.
This function takes
a char array, an integer pointer, a char for the start node, and a char
for the end node.
The char array is how the
path is passed back to the calling function. The int pointer is how the
path distance is passed back.
The algorithm works as follows:
It sets the current node
equal to the starting node.
Enters loop
Checks the current nodes links, and sets their distances from the startnode,
makes them tentative, sets their previous node to the current node.
Outputs the link nodes' tentativity. (try saying that with a few pints
in you ;-)
Makes the current node permanent, now that all links have been tried.
Outputs the current nodes permanence.
Goes through all tentative nodes and selects the one with the smallest
distance from startnode,
Sets this node as the current node for the next iteration.
Sets the shortest known distance.
Exits loop when current
node is the end node
It then back tracks through
network, following the previousNode pointer of each node,
copying the path into an
array as it goes.
This array is backwards,
so it must be reversed before returning the answer.
The path, and the distance
are returned by the function.
readNodes Function
This function takes a filename and a Network
object as parameters.
It opens the file and adds the appropriate Nodes
and links the the supplied Network Object.
It returns a bool to represent success or failure.
main Function
It makes sure the parameters are correct,
creates a Network object, then calls readNodes to initialise that network.
If readNodes returns true, it creates a path array
and distance integer to store the results.
It calls the getShortestPath function of the Network
Object, supplying the above variables, then prints the results.
If readNodes returns false, it prints an error that
the file couldn't be opened, then exits.
Routing Example
James O' Connor 50703338 31/10/2002