Dijkstra's Shortest paths

Introduction

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.

Getting an Intuition for the Algorithm

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.

  1. The node has never been visited and the distance is to the source is unknown
  2. One or more paths have passed through the node and it has a tentative shortest path.
  3. 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.

images/grf1_002.png images/grf1_004.png

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).

images/grf1_007.png images/grf1_009.png

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.

images/grf1_010.png images/grf1_012.png

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

Animated (return with the browser's Back button)

The Code

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.

Displaying the Algorithm in Operation

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

Shortest path between any two points

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.

Running the program

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()

Running Dijkstra in Graphic mode.

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

.