Introduction

A network topology can be represented by a graph -- each node is a server and each edge is network connection.  To determine the best way to route a data packet from your server to anywhere on the internet, you need to know the shortest path to each node.  This problem is known as the shortest-paths problem, and it can be solved by Dijkstra's algorithm.
 

Resources

• To see Dijkstra's algorithm in action, follow this link and try the applet demos.  To animate the applets, click on them.  The first click will highlight the start node.  The next click will expand the start node and determine a first estimate of the shortest distance to each of its neighbours.  Clicking again, the visited (but unexpanded) node with the shortest distance estimate will be selected.  Subsequent clicks will alternate between expanding nodes and selecting the next node to expand.
• If you would like to create your own graphs for Dijkstra's algorithm, try this example.  Notice that the edge weights are directed (and can be asymmetric).
• Since the the next node to select is based on the current distance estimates, the nodes should be stored in a heap.  This example shows Dijkstra's algorithm with its priority queue.