## Network Algorithms

Authors: Alex Tee Neng Heng, David G. Green

This demonstration allows you to run through various well-know graph algorithms step-by step which may be very helpful for understanding how these algorithms work. The demo allows you to study the following algorithms:

• MST (minimum spanning tree): Given a connected, undirected graph G, a spanning tree T of G is a sub-graph of G, such that:
T which is a tree (i.e. a graph in which any two vertices are connected by exactly one path) and
T connects all of the G‘s nodes.
A graph can have several spanning trees. A minimum spanning tree Tmin of a connected, undirected and weighted graph G is a spanning tree of G such that the weight-sum on the edges of Tmin is less than or equal to the weight-sum of any other spanning tree of G.
This simulation demonstrates two different algorithms for finding the MST of a graph: Prim’s algorithm and Kruskal’s algorithm.
• Shortest path is the problem of finding a path with minimal weight-sum that connects all nodes (Dijkstra’s algorithm is used here).
• Diameter is the problem of finding the path with the maximum weight-sum that does not visit a node more than once (Dijkstra’s algorithm is used here).
• Circuit is the problem of finding shortest closed loop (depth first search algorithm is used here).
• Breath first search is a standard graph algorithm often used for funding the closest distance between two nodes.

### How to use the simulation

1. Specifying the network: You can either automatically create one of several types of networks or explicitly specify the configuration of your graph.
• To specify your graph explicitly: edit the connection weights at the bottom of the control panel and then click Apply Weights. Alternatively, you can automatically create of of the 4 graph types:
• Random network: the distribution of nodes is approximately uniform, the only parameter is the connectivity;
• Tree: is a network with branches stemming off a single â€œrootâ€, the main parameter is the number of branches;
• Small world: is a regular network with a degree of random â€œlong rangeâ€ connections;
• Scale free network: is one in which the distribution of links per node follows a power law distribution;
2. Set the problem: Select one of the problems described above.
3. Start the simulation: Click the Start button. Each algorithm step will be illustrated on the graph depicted in the simulation window and explained in the text field at the bottom.