Shortest path routing/Catalogs/Dijkstra59.py

This is an annotated version of the program in Shortest path routing, with notes for students not yet familiar with Python. You can run this code using an interpreter from python.org, version 3.0 or later.

# dijkstra59v05_A.py            Dijkstra's Algorithm                DMQ 12/23/09
'''
Use Dijkstra's algorithm to compute the shortest paths from a given source node
to all other nodes in a network. Links are bi-directional, with the same
distance in either direction.  Distance can be any measure of cost.

Python Notes:
This program will make good use of Python's standard data structures - sets,
lists, and dictionaries. Sets have curly brackets, and lists have square
brackets.  Tuples have parentheses.  Tuples are immutable lists.  They behave
like lists, except there are no methods to change the items in a tuple.
~'''

# Example from Figure 1 (8 nodes, 11 links)
nodeset = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}

linklist = [('A', 'B', 2), ('B', 'C', 7), ('C', 'D', 3), # (node,node,distance)
            ('B', 'E', 2), ('E', 'F', 2), ('F', 'C', 3),
            ('A', 'G', 6), ('G', 'E', 1), ('G', 'H', 4),
            ('F', 'H', 2), ('H', 'D', 2),               ]

INF = int(1e9)  # larger than any possible path
'''
The strategy is to start at the source node, send probes to each of its adjacent
nodes, pick the node with the shortest path from the source, and make that the
new working node.  Send probes from the new working node, pick the next shortest
path, and make that the next working node.  Continue selecting the shortest
possible path until every every node in the network has been selected.

Figure 1 shows the first few steps in our example network. Labels on each node
show its distance from the source, and the previous node on the path from which
that distance was computed.  As new nodes are first probed, they are added to a
working set, shown with a darkened open circle.  After each probe cycle, we look
at the entire set of working nodes.  The node with the shortest path is moved to
a final set, shown with a solid circle.  Figure 1b shows the situation after the
first probes from node 'A', with one node in the final set, and two nodes in the
working set.

The labels on nodes in the working set are tentative.  They will be replaced if
another probe arrives with a shorter total path.  Figure 1d shows node G getting
an update of its label after a probe from node E.  The updates at a node stop
when no other working set node has a shorter path.  This is the proof that the
method works.  The node with the shortest path in a working set can never get
any shorter, because subsequent probes can only come from other working nodes,
and those paths are already at least as long.  There are no negative links.

Figure 1i shows the final tree for node A.  The light dotted lines are links not
used in any shortest path from node A.  They might be used in another tree,
however.  Each node in a network can compute its own shortest path tree, given
the linklist for the entire network.
~'''

def get_LSDB(nodeset, linklist):
    '''Create a Link State Database to quickly look up the adjacent nodes for
any given node.

>>> get_LSDB(nodeset, linklist)
{'A': {('B', 2), ('G', 6)}, 'C': {('B', 7), ('F', 3), ('D', 3)}, \
'B': {('C', 7), ('E', 2), ('A', 2)}, 'E': {('B', 2), ('G', 1), ('F', 2)}, \
'D': {('H', 2), ('C', 3)}, 'G': {('A', 6), ('E', 1), ('H', 4)}, \
'F': {('H', 2), ('E', 2), ('C', 3)}, 'H': {('G', 4), ('D', 2), ('F', 2)}}

Python Notes:
This database is implemented as a Python dictionary, a set of {key: value}
pairs.  The keys in this case are just the names from the nodeset.  The values
are the set of nodes connected to each key node.  Notice how easily we can nest
data structures in Python.  Here we have a dictionary of sets of tuples.

The multiline string (enclosed in triple quotes) at the start of each module or
function is called the "docstring".  It is used in generating automatic
documentation.  The example code snippets are called "doctests".  They look just
like what you will see when you call the function from an interactive prompt
(>>>).  The example above was created using a copy-and-paste from an interactive
session (adding a few \ end-of-line escapes to make the single line of real
output appear within the margins of our docstring).

Doctests are not only excellent ways to explain what your function does, but
they also serve as unit tests, running automatically and alerting you when some
change you just made breaks the existing doctests.

    ~'''
    LSDB = {n:set() for n in nodeset} # start with empty set for each node
    for (n1, n2, d) in linklist:
        LSDB[n1].add((n2, d))
        LSDB[n2].add((n1, d))
        
    return LSDB

'''
Python notes:
The code above shows a number of elegant features of Python.  The syntax to
create a dictionary of sets reads very much like set notation in mathematic {a
dictionary with an empty set for each node in nodeset}.  See
[http://en.wikipedia.org/wiki/Set-builder_notation Set-builder notation] for
more examples.

When you need to assign items in a structure, each to a simple variable, you can
do it all at once by putting the variable names in a tuple on the left side of
the assignment operator.  Each item from linklist is a triple, and it is
automatically unpacked and assign to the names in the triple on the left.

Finally, notice how easily we can add complex structures to a dictionary or set,
without a mind-boggling set of indices on multiple levels.  The add method adds
one item to a set.  The inner parens make a pair of items into one.

At this point, you may be thinking, lets just do it in C.  Trust me.  Once you
feel comfortable with Python's basic data structures, the four lines above will
be very intuitive, and you will avoid having to wrestle with all the low-level
details of having a special structure for each new problem.
~'''

def build_tree(src, LSDB):
    '''Given a source node and a Link State Database for the network, return a
table with two values for each node - the distance on the shortest path from the
source to that node, and the name of the last node on that path before the final
node.  Saving the previous node makes it easy to re-construct an entire path,
from any leaf to the root of the tree.

>>> build_tree('A', LSDB)
{'A': ('A', 0), 'C': ('B', 9), 'B': ('A', 2), 'E': ('B', 4), \
'D': ('H', 10), 'G': ('E', 5), 'F': ('E', 6), 'H': ('F', 8)}

    ~'''
    # Current working node
    wrk = src
    
    # Nodes in the working set and final set, saved as dictionaries.
    #   {key: value} = {nodename: (previous node, distance from src) }
    Wset = {}; Fset = {}
    Wset[wrk] = (wrk, 0)            # {'A': ('A', 0)}

    while Wset:  # loop until the work set is empty
  
        # Select next wrk node
        dist = INF
        for node in Wset:           # Find the shortest distance in the
            (prev, d) = Wset[node]  # working set, and make that node the
            if d < dist:            # new working node. The distance of that
                dist = d            # node will never get smaller.
                wrk = node
        
        # Move the new working node to the final set.        
        Fset[wrk] = Wset[wrk]
        del Wset[wrk]
        last = wrk                  # last node before end of path

        # Expand the work set
        for (n, d) in LSDB[wrk]:      # Probe the nodes adjacent to wrk      

            new_dist = dist + d          # probe distance
            
            if n in Fset:
                continue                 # skip this node, already finalized
            
            elif (n in Wset) and (new_dist >= Wset[n][1]):
                continue                 # skip this node, probe too long           

            else:  # Add new node to working set, or update existing node
                Wset[n] = (last, new_dist)
    
    return Fset

def build_RT(src, LSDB):
    '''Given a source node and a Link State Database for the network, return a
table with three values for each node - the distance on the shortest path from
the source to that destination node, and the names of the first and last nodes
on the path, not including the endpoints.  The first node is needed in a routing
table.  The last node is needed to construct a tree with src at the root.

>>> build_RT('A', LSDB)
{'A': ('A', 'A', 0), 'C': ('B', 'B', 9), 'B': ('B', 'A', 2), \
'E': ('B', 'B', 4), 'D': ('B', 'H', 10), 'G': ('B', 'E', 5), \
'F': ('B', 'E', 6), 'H': ('B', 'F', 8)}

    ~~'''
    # Current working node
    wrk = src
    
    # Nodes in the working set and final set, saved as dictionaries.
    #   {key: value} = {nodename: (first, last, distance from src)}
    Wset = {}; Fset = {}

    # Special setup for first step
    Fset[wrk] = (wrk, wrk, 0)      # {'A': ('A', 'A', 0)}
    for (n, d) in LSDB[wrk]:
        first = n                  # first step on the new route
        last = wrk
        Wset[n] = (first, last, d) # {'B': ('B', 'A', 2), 'G': ('G', 'A', 6)}

    while Wset:  # loop until the working set is empty
  
        # Select next wrk node
        dist = INF
        for node in Wset:           # Find the shortest distance in the
            (first, last, d) = Wset[node]  # working set, and make that node
            if d < dist:            # the new working node. The distance of
                dist = d            # that node will never get smaller.
                wrk = node
        
        # Move the new working node to the final set        
        Fset[wrk] = Wset[wrk]
        del Wset[wrk]
        # Update first and last hops
        first = Fset[wrk][0]
        last = wrk

        # Expand the work set
        for (n, d) in LSDB[wrk]:      # Probe the nodes adjacent to wrk      

            new_dist = dist + d          # probe distance
            
            if n in Fset:
                continue                 # skip this node, already finalized
            
            elif (n in Wset) and (new_dist >= Wset[n][2]):
                continue                 # skip this node, probe too long           

            else:  # Add new node to working set, or update existing node
                Wset[n] = (first, last, new_dist)
    
    return Fset

def get_path(dest, RT):
    '''Given destination node and a Routing Table, return the shortest path
from the top of the tree to dest, and the total distance along that path.

>>> get_path('D', RT)
(['A', 'B', 'E', 'F', 'H', 'D'], 10)

    ~'''
    wrk = dest              # Work backward from the destination node.
    last = RT[wrk][1]       # one step back
    path = [wrk]
    dist = RT[wrk][2]
    
    while wrk != last:      # top has no step back (wrk = last)
        path.insert(0, last)    # insert at beginning of list
        wrk = last
        last = RT[wrk][1]

    return path, dist


if __name__ == '__main__':  # Test Bench setup

    class G: pass  # Global variables for diagnostics
####    G.numloops = 0                                                        ###
##    while Wset:  # loop until the working set is empty
####        print(len(Wset), end=' ')                                         ###
####        print(len(Wset), Wset)                                            ###
####        G.numloops += len(Wset)                                           ##
    
# Example 1 - small network
    nodeset = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}

    linklist = [('A', 'B', 2), ('B', 'C', 7), ('C', 'D', 3),
                ('B', 'E', 2), ('E', 'F', 2), ('F', 'C', 3),
                ('A', 'G', 6), ('G', 'E', 1), ('G', 'H', 4),
                ('F', 'H', 2), ('H', 'D', 2),               ]

    LSDB = get_LSDB(nodeset, linklist)  # Link State Database

    RT = build_RT('A', LSDB)           # Routing Table

# Example 2 - bigger networks
    from random import randint  # for generating random integers
    from time import time

    for size in range(500, 1500, 500):
    
        t0 = time()
        nodeset1 = set(range(size))
        t1 = time()
        
        linklist1 = []
        for n1 in nodeset1:
            for lnk in range(3):   # 3 links per node
                n2 = randint(0, size-1)  # anywhere in network
                if n1 == n2: continue         # no link to self
                distance = abs(n1 - n2)
                link = (n1, n2, distance)
                if (n1, n2, distance) in linklist1: continue  # no duplicates
                if (n2, n1, distance) in linklist1: continue  
                linklist1.append(link)
        t2 = time()
        
        LSDB1 = get_LSDB(nodeset1, linklist1)
        t3 = time()

        RT1 = build_RT(1, LSDB1)
        t4 = time()

        print (size, t4-t3, len(linklist1))

    
    from doctest import testmod
    testmod(verbose=True)