The algorithm to compute the shortest paths from a source node to each of the other nodes was discovered by the Dutch computer scientist Edsger Dijkstra in the 1950's. He used it as a demonstration program for a new computer. The program contained a graph of 63 Dutch towns connected by roads. A user could input a starting town and a destination and the computer would calculate the shortest route through the towns. So, basically Google Maps Driving Directions, version 0.1

The problem is simple if the number of nodes is very small, say five or so. But like the length of a lottery number, each additional node increases possibilities exponentially. At 63 nodes no computer could hope to do this in a simple minded way, even today.

Dijkstra's algorithm works by visiting nodes out from the source in a rather unusual way. It is surprisingly fast, given that it finds the shortest paths to all of the nodes simultaneously.

All nodes may be in one of three states while the exploration is underway.

- The node has never been visited and the distance is to the source is unknown
- One or more paths have passed through the node and it has a tentative shortest path.
- The shortest path to the node is fixed since it is no longer possible for a still shorter path to be found.

The key idea is how we get nodes from state 1 to state 2. And it is this.

At any point, the one tentative node (state 1) with the shortest distance to the source may be immediately promoted to state 2. Think about it. If an even shorter path were to be found in the future then it must pass through a tentative node that is already longer. But that is a contradiction.

Once this shortest node (call it x) is promoted to state 2, all of its neighbors may be checked. Those in state 0 can now be set to state 1 with a tentative distance computed by adding the length of the connecting edge to the (now) fixed distance of x. Neighbors already in state 1 may perhaps get their distances shortened.

We keep going until there are no nodes in state 1.

The images below show a simple example. From the source node labeled *S* we want to find the shortest path to each of the four other nodes *A, B, C, D* using the 5 edges in green. The numbers in blue show the length of each edge connecting two nodes. The nodes are labeled in colors indicating their status. A node is green if it has not been visited (state 0), orange if in state 1 and red in state 2. In states 1 and 2 the current distance to source is shown along with the name of the node.

To see the algorithm at work, we will examine a very simple graph. The figures below form an animation. We'll look at just a subset.

We start with Figure 2. S is our source node and was set to state 1. Then to state 2 since it is the closest node with a distance of zero. All the other nodes are still in green (state 0) with no known distance. With S as our first hub, its neighbors A and B are set to orange (state 1) with tentative distances equal to the edges connecting them to S (Figure 4).

Now since A is closer to the source than B, it is chosen as the next hub and expanded to bring tentative distances to C and D. These distances are both 66. (46+20).

Next, node B is now the closest tentative. It goes red, looks at neighbor C and since it can provide a shorter distance (65 instead of 66) it updates node C to 65. This is a key step. See fig-9.

Coming into the home stretch now. Node C is now the closest orange and is set to red (state 2). It has no neighbors in a lower state so it's done (Figure 10). Node D is likewise dispatched and we are done. (Figure 12). The graph is complete with every node in state 2 with its final distance to the source fixed.

To see this in a little GIF movie, click on the animation link

The program dijkstra.py may be run stand-alone in a text mode. This keeps things pretty simple. The graphics displayed above use the sarg, camera and pgcon modules which are described in the pgame support library

The program code shown below is available as dijkstra.py. The whole package including the graphics modules can be downloaded as a zip file.

First, let's look at how nodes are represented by *Node* instances.

# dijkstra.py 09 class Node : 10 def __init__ (self, name, pos, nbrs=[]) : 11 self.name = name 12 self.pos = pos 13 self.nbrs = [] # list of neighbor nodes and distance (tuples) 14 self.reset() 15 16 def reset(self) : 17 self.srcDist = maxint # tentative distance to source unknown 18 self.prev = None # 1st node going back to source 19 self.state = 0 # distance is 0=unknown, 1=tentative or 2=fixed 20 21 def __str__(self) : 22 nbrs = [nbr.name for nbr,dist in self.nbrs] 23 return "%s: %s" % (self.name, nbrs) 24

The attributes of a node are simply its position (x,y) in pixels, name (uppercase), distance from the source node (or maxint), a list of neighbors (other nodes), the previous node in the path back to the source node, and its current state. At the beginning all states are in state zero and when the process is complete they are all in state two.

In state 0, the distance to the source node is set as high as possible. *sys.maxint* is the largest integer value for the word size of your computer. When a node is first set to state 1, the distance will be "improved".

The *nbrs* list is actually composed of tuples with the 1st item a reference to a connected node and the 2nd item the length of the connecting edge. This forms a double link. If node *A* is a neighbor of node *B* then node *B* is also a neighbor of *A*.

Let's look at how a graph is created. A module that contains a function *makeGraph* is imported by *main* in dijkstra.py. Here's how our simple example was built.

# graph_1.py 03 def makeGraph (Node) : 04 nodeList = [ 05 Node("S", (150, 50)), 06 Node("A", ( 50,150)), 07 Node("B", (200,200)), 08 Node("C", (150,230)), 09 Node("D", ( 50,250))] 10 11 nodeDict = {} 12 for node in nodeList : 13 nodeDict[node.name] = node 14 15 edges = [ 16 ("S","A",46), 17 ("S","B",55), 18 ("A","C",20), 19 ("A","D",20), 20 ("B","C",10)] 21 22 for nam1,nam2,incDist in edges : 23 nod1 = nodeDict[nam1] 24 nod2 = nodeDict[nam2] 25 nod1.nbrs.append( (nod2,incDist) ) 26 nod2.nbrs.append( (nod1,incDist) ) 27 28 return nodeList, nodeDict

Function *makeGraph* simply takes the class definition for *Node* and creates a list of nodes on the fly. (lines 4-9). It also creates a dictionary *nodeDict* to access to access nodes by their name. Variable *edges* is a list of edges between nodes and is used in the *for* loop to create the *nbrs* (neighbors) list in Node pairs. (lines 22-26). When finished, the funtion returns both the list and dictionary of completed nodes.

The function *findPaths* is at the heart of the program. If you followed the logic of the algorithm above, the code should be straight-forward.

For now, ignore calls to the function *display* and the setting of variables *banner* and *action*.

# dijkstra.py 25 def findPaths(nodes, source) : # node names 26 "implements the dijkstra algorithm. Updates nodes dist & prev attributes" 27 for node in nodes : node.reset() 28 source.srcDist = 0 29 source.state = 1 30 display("Initial Configuration", nodes) 31 while True : 32 best = maxint; hub = None 33 for test in nodes : 34 if test.state != 2 and test.srcDist < best : 35 best = test.srcDist 36 hub = test 37 if not hub : break # all nodes in final state 38 hub.state = 2 # set hub as final 39 display("Node "+hub.name+" set to fixed state",nodes) 40 for nbr,incDist in hub.nbrs : 41 if nbr.state == 2 : continue # already finalized 42 if nbr.prev == hub: continue # no looking back ! 43 if hub.srcDist+incDist < nbr.srcDist : 44 if nbr.state == 0 : action = "sets tentative distance to" 45 else : action = "overrides distance to" 46 nbr.state = 1 # tentative capture 47 nbr.srcDist = hub.srcDist+incDist 48 nbr.prev = hub 49 else : 50 action = "can't improve distance to source" 51 banner = "%s %s %s" % (hub.name,action,nbr.name) 52 display(banner,nodes) 53 display("Shortest Paths from %s" % source.name, nodes)

Function *findPaths* is passed a list of all the nodes in the graph and the source node.
Initializaion is done in lines 27-29. All nodes are reset and the source node is set up to get things going. The main loop starts at line 31. A *hub* node in sought. The hub will be in state 1 and have the smallest tentative distance to the source. On the first pass through the loop this will be the source node itself. While testing the candidates in the loop at line 33, the variable *hub* tracks the node with the *best* lowest distance so far.

If no hub node is found, we are done. Otherwise the hub node is promoted to state 2 (line 39). Its neighbors are scanned (line 40) and those that are new or tentative will have their best distance to source (line 47) set. New nodes also have their status set to tentative.

Dijkstra.py can be run in either a text or graphic mode. The variable *display* above points to the appropriate function. For text output we have the following.

# dijkstra.py 55 fig = 0 56 57 def displayText (banner, nodes) : 58 global fig 59 fig += 1 60 print "Fig %d: %s" % (fig,banner) 61 for node in nodes : 62 dist = node.srcDist 63 if dist == maxint : dist = "Unknown" 64 print " %s state=%s toSource=%s" % (node.name,node.state,dist) 65

And this is a run for the graph above, partially truncated.

$ python dijkstra.py graph_1 text S ... Fig 2: Node S set to fixed state S state=2 toSource=0 A state=0 toSource=Unknown B state=0 toSource=Unknown C state=0 toSource=Unknown D state=0 toSource=Unknown Fig 3: S sets tentative distance to A S state=2 toSource=0 A state=1 toSource=46 B state=0 toSource=Unknown C state=0 toSource=Unknown D state=0 toSource=Unknown ... Fig 9: B overrides distance to C S state=2 toSource=0 A state=2 toSource=46 B state=2 toSource=55 C state=1 toSource=65 D state=1 toSource=66 Fig 10: Node C set to fixed state S state=2 toSource=0 A state=2 toSource=46 B state=2 toSource=55 C state=2 toSource=65 D state=1 toSource=66 ... Fig 12: Shortest Paths from S S state=2 toSource=0 A state=2 toSource=46 B state=2 toSource=55 C state=2 toSource=65 D state=2 toSource=66

Function *findPaths* sets not only the distance back to the source node but also a reference to the previous node in the path in the *prev* attribute. If we want to build a path from the source to an given node, we must first construct the path back to the source by using the chain of previous nodes. This builds the path (as a list) in reverse.

If we just want a path from A to B, we can run *findPaths* with B as the source, look up A and construct the path back to B. But running *findPaths* for each look-up would be expensive. It might be better to cache results in a dictionary. Paths can be stored in a a simple string, for example, with names seperated by by dashes.

Here is a function *findAllPaths* that lists all paths between node pairs. It also returns of all paths in a cache.

66 def findAllPaths(nodes) : 67 paths = {} # memoize paths here 68 for source in nodes : 69 findPaths(nodes, source) 70 for end in nodes : 71 if end != source : 72 distance = end.srcDist 73 walk = end; path = [] 74 while True : 75 path.append(walk.name) 76 if walk == source : break 77 walk = walk.prev 78 path = list(reversed(path)) 79 path = '-'.join(path) 80 key = "%s-%s" % (source.name,end.name) 81 paths[key] = path 82 print "For %s dist=%s use %s" % (key,distance,path) 83 print 84 return paths 85 86 def displayOff (banner, nodes) : pass

For each source node (line 68) we find all paths back to it. Ignoring a path from the source, we walk back from each destination building a path in reverse (71-77). When the source is reached the path is reversed (line 78) and converted into a string (79). A dictionary *paths* stores the paths for each pair of source and destination and is returned by the function.

The *display* calls from *findPaths* directed to *displayOff* when *findAllPaths* is run from *main*. There they are ignored (86).

Here is an example

$ python dijkstra.py graph_1 all For S-A dist=46 use S-A For S-B dist=55 use S-B For S-C dist=65 use S-B-C For S-D dist=66 use S-A-D For A-S dist=46 use A-S For A-B dist=30 use A-C-B For A-C dist=20 use A-C For A-D dist=20 use A-D For B-S dist=55 use B-S For B-A dist=30 use B-C-A For B-C dist=10 use B-C For B-D dist=50 use B-C-A-D For C-S dist=65 use C-B-S For C-A dist=20 use C-A For C-B dist=10 use C-B For C-D dist=40 use C-A-D For D-S dist=66 use D-A-S For D-A dist=20 use D-A For D-B dist=50 use D-A-C-B For D-C dist=40 use D-A-C

Having a dictionary of paths keyed by their start-end is very useful. In this form it is simple to pick apart the segments with their distances as well. We could give driving directions with the distance of each segment.

Also, a minor point. If we have a path for B-D (B-C-A-D) stored, we really don't need to compute and store the path for D-B. Just reverse the key and reverse the value.

The function *main* is invoked when run from the terminal window. The first argument is always the graph file to be imported (without .py) and the second is the display mode (text, all, pygame). A third argument is needed for text and pygame modes to indicate the source node.

88 def main() : 89 global display 90 displayMode = argv[2] 91 nodes, nodeDict = graph.makeGraph(Node) 92 if displayMode == "all" : 93 display = displayOff 94 paths = findAllPaths(nodes) 95 else : 96 source = argv[3] 97 if displayMode == "pygame" : 98 import display_pygame 99 display = display_pygame.display 100 findPaths(nodes, nodeDict[source]) 101 display_pygame.display_close() 102 else : 103 display = displayText 104 findPaths(nodes, nodeDict[source]) 105 106 if __name__ == "__main__" : main()

The module *display_pygame.py* provides a display function that created the images and gif seen at the beginning. We wont go into detail here. The use of the pygame graphics is explained the "Minimum spanning tree" project and its use here is similar. If you have pygame installed then the following commands are some examples.

$ python dijkstra.py graph_1 pygame S pixels=300 Hit Return to Continue $ python dijkstra.py graph_2 pygame S pixels=400 Hit Return to Continue $ python dijkstra.py graph_1 S pixels=300 maxpics=25 prefix=graf1 gif=1 fontsize=24

You can download the zip file for dijkstra here

If you have comments or suggestions You can email me at mail me

Copyright © 2014-2019 Chris Meyers