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.

Links and References

Demo screenshot