Data Structures
Project: Shortest Paths and MST for a Network Communication System
Any network system is composed of many routers, servers and system users that can be
represented by a routers’ graph. In Routers’ Graph, each node represents one router. This graph is a
weighted graph, whose weights represent the distances of the two connected routers in meters.make a Routers’ Graph to apply some useful algorithms on it. This Graph
must be stored in orthogonal List.
Finding Minimum Distances
In Network Communication System, the shortest path between the transmitter and receiver is
of most importance. Dijkestra Algorithm can suggest the shortest path between any two nodes
which are linked together by at least one path. You have to implement Dijkestra’s Algorithm to
find the shortest path between one transmitter and all other existing nodes in the Routers’ graph.
The source node will be selected by the user and then your program must apply the Dijkestra
algorithm to find the minimum distances from that source to all other possible destinations in the
graph.
Finding Minimum Spanning Tree
In this Network Communication System, the Minimum Spanning Tree (MST) of the Routers’
Graph is also important because they want to setup a network between routers, servers and system
users. The MST will help them in achieving the least cost for transmission.implement the
Kruskal’s Algorithm to find the MST of the routers’ graph. The root node of the tree will be
selected by the user and then your program must apply the Kruskal’s Algorithm to find the MST of
the routers’ graph.
Inputs
There must be only two ways for your program to get input:
1- From file following the specified file format
2- Generation of random graph (Use edge number or edge density for this purpose)
a. Number of Routers. (Which will generate Router1, Router 2, Router 3,..., Router N)
b. Fixes Distance range i.e. 10 - 100 meter (between any two cities)
Outputs
Following are the required outputs from your project:
1- Draw Routers Graph on Screen
2- Draw Graph after applying Dijkestra Algorithm on Screen
3- Draw MST after applying the Kruskal’s Algorithm.
4- All of the above diagrams must be labeled with Router Name and Weight.
5- Write the Graph after applying Dijkestra Algorithm on Dijkestra.txt in the specified format.
6- Write the MST after applying Kruskal’s Algorithm on Kruskal.txt in the specified format.
Graph Modification
The following modifications must be allowed for the user to perform on the loaded/generated
graph.
1- Add Node without necessarily adding a path
2- Add Edge between any two nodes
3- Modify any Edge’s weight
4- Modify any Router Name
5- Delete Edge (Modifying edge to 0 meter must delete the node)
6- Delete Router Node (This must also delete all associated edges)
Please note that the length of any edge in your drawing does not represent the weight of that
edge. Although the weight must be labeled using Textout function.
Files Formats
The following formats must be strictly followed by all the teams. make sure that
your program creates the text files that exactly follow the same pattern specified below.
Input Files
1- Graph Input File Format
First line is list of names of Routers. All subsequent lines represent edges in the graph with
their weights e.g. consider following input file.
In the above graph there are four cities R_L1072, R_L1073, R_L1074 and R_L1075. Distance
between R_L1072 and R_L1073 is 1000, distance between R_L1074 and R_L1075 is 10.
[R_L1072][ R_L1073][ R_L1074][ R_L1075]
[0-1][1000]
[1-2][1400]
[1-3][1400]
[2-3][10]
[Router Name 1][ Router Name 2][ Router Name 3]…..[ Router Name n]
[0-1][50]
[1-2][20]
[1-3][80]
[2-3][20]
Output Files
1- Dijkestra.txt
2- Kruskals.txt
[Source Router]
[Router Name1:Path Distance]: {Source Router, Intermediate Router 1, Intermediate Router 2, …… Router Name 1}
[Router Name2:Path Distance]: {Source Router, Intermediate Router 1, Intermediate Router 2, …… Router Name 2}
……
…...
[Router Name1, Router Name2][ Router Name x, Router Name y]……….[ Router Name m, Router Name n]
[Total weight of tree]