Enter Source Node
Enter Destination Node
Note that plotting a random or tree style network will take a few seconds.
This is due to the physics simulation required create the layout. Nodes repel other nodes, and links pull them together.
Curious about what the web app above is doing?
This web app creates networks, also called graphs, which are mathematical constructs that show relationships, or "links," between entities. Nodes that have a link between them are called "neighbors." Then, given a source and destination node (the dots that appear), it systematically searches for the shortest path between the two. Pressing the "Shortest Path Step" button will display the next node in the search for the destination and pressing it after reaching the destination will cause the path to display.
The types of Networks available here:
A random graph, or Erdős–Rényi Graph, is a graph that uses two parameters: n and M. The n reflects the number of nodes that will be in the graph; you can change this with the drop-down menu at the top of the control panel. The M parameter is the probability of a link between any two given nodes. It is pre-defined, as it is easy to get graphs that would not be very easy to visualize or work with.
A tree network starts with a single node, and repeatedly branches into additional nodes. In this web app it always branches into two more nodes and stops at the third iteration.
A grid network, or lattice graph, is one where nodes that are not on an edge will have 4 neighbors. A node on the edge of a lattice, but not at a corner, will have 3 neighbors, and the corners each have 2 neighbors. Lattice networks do not have to be squares; one where interior nodes have 6 neighbors, edge nodes have 4 neighbors, and corner nodes have 2 neighbors would be made up of triangles.
Shortest Path Algorithm
The algorithm used to find the shortest path is based on Dijkstra's algorithm. The algorithm is, for unweighted graphs like the ones on this page, described plainly as follows:
[Node 2, Node 1]
[Node 3, Node 2]
[Node 4, Node 3]
If we were trying to get from Node 1 to Node 4, it is easy to see that we can go along the path:
[Node 1, Node 2, Node 3, Node 4].
Additional Resources:
This is due to the physics simulation required create the layout. Nodes repel other nodes, and links pull them together.
Curious about what the web app above is doing?
This web app creates networks, also called graphs, which are mathematical constructs that show relationships, or "links," between entities. Nodes that have a link between them are called "neighbors." Then, given a source and destination node (the dots that appear), it systematically searches for the shortest path between the two. Pressing the "Shortest Path Step" button will display the next node in the search for the destination and pressing it after reaching the destination will cause the path to display.
The types of Networks available here:
A random graph, or Erdős–Rényi Graph, is a graph that uses two parameters: n and M. The n reflects the number of nodes that will be in the graph; you can change this with the drop-down menu at the top of the control panel. The M parameter is the probability of a link between any two given nodes. It is pre-defined, as it is easy to get graphs that would not be very easy to visualize or work with.
A tree network starts with a single node, and repeatedly branches into additional nodes. In this web app it always branches into two more nodes and stops at the third iteration.
A grid network, or lattice graph, is one where nodes that are not on an edge will have 4 neighbors. A node on the edge of a lattice, but not at a corner, will have 3 neighbors, and the corners each have 2 neighbors. Lattice networks do not have to be squares; one where interior nodes have 6 neighbors, edge nodes have 4 neighbors, and corner nodes have 2 neighbors would be made up of triangles.
Shortest Path Algorithm
The algorithm used to find the shortest path is based on Dijkstra's algorithm. The algorithm is, for unweighted graphs like the ones on this page, described plainly as follows:
Specify Source Node
Create a list of Unvisited Nodes (without the Source Node)
Create a Queue (with the Source Node in it)
Create a History Table
While the Queue is not empty:
Set the first Node in the Queue as the Active Node
Remove the first Node from the Queue
For each Neighbor of the Active Node that is in the Unvisited List:
Remove the Neighbor from the Unvisited List
Add the Neighbor to the Queue
Add [Neighbor, Active Node] to the History Table
If the Neighbor is the Destination, END
From the resulting History table, then, it is possible construct the actual shortest path. It would resemble the following example:Create a list of Unvisited Nodes (without the Source Node)
Create a Queue (with the Source Node in it)
Create a History Table
While the Queue is not empty:
Set the first Node in the Queue as the Active Node
Remove the first Node from the Queue
For each Neighbor of the Active Node that is in the Unvisited List:
Remove the Neighbor from the Unvisited List
Add the Neighbor to the Queue
Add [Neighbor, Active Node] to the History Table
If the Neighbor is the Destination, END
[Node 2, Node 1]
[Node 3, Node 2]
[Node 4, Node 3]
If we were trying to get from Node 1 to Node 4, it is easy to see that we can go along the path:
[Node 1, Node 2, Node 3, Node 4].
Additional Resources: