MATH 3600 HW25

2782 days ago by kcbrenn

MATH 3600 - HW25

 

Your name: Kyle Brennan, Hannah Kimbrell, Justin Ulmer

 

Date: April 21, 2014

Graphs

A graph is an ordered pair, G = (V,E), where V is a set of vertices and  E = {{u,v} | u ε V and v ε V} is the set of Edges.  

More precisely, E is a collection of subsets of V, each of size 2, and the elements of E are called edges.

We will start be defining the class of Graph objects. This class will store V and E as sets.  The vertices can be any kind of immutable object.  The edges in E will be ordered pairs (tuples) of vertices.  Tuples have the advantage of being immutable objects.  This use of immutable objects will allow us to implement the several of the methods of the Graph class using Python's extremely efficient Dictionary class.

A Graph will own the sets V and E which define it. By using the set class for V and E we eliminate the concern about multiple copies of a vertex.  It is also that case that a tuple (u,v) cannot be accidentally stored more than once, but we will need to avoid accidentally storing both (u,v) and (v,u). A Graph will also own a Dictionary called Adj, which is a particularly efficient data structure for algorithms that would naturally exploit the relationships stored in the Adjacency matrix.  It also provides an efficient record of the degree for each vertex. V, E, and Adj are not treated as private objects so that we can directly explore possible algorithms which use them.

In HW13 we introduced the initial version of the Graph class which was very limited while we began to explore methods to be added to the class.  Methods which are both relevant to the effective use of Graphs and capable of being efficiently implemented. In that homework we developed a code for plotting a graph and two codes for determining if a graph is connected. One approach was a recursive code that used a depth-first search. The second approach used a queue and a breadth first search. The Graph class in this homework incorporates what we learned by including methods for plotting the graph, for determining whether the graph is connected, and for creating a list of the components of the graph. These last two methods are based on the breadth-first search algorithm, which requires that we include the code for the Queue class.

Be sure to check out this new Graph class by doing tab completion on one or more of the Graph objects that you create.

class Graph(object): '''Represents a graph''' def __init__(self, vertices, edges): '''A Graph is defined by its set of vertices and its set of edges.''' self.V = set(vertices) self.E = set([]) self.Adj = {} self.add_edges(edges) print '(Initializing a graph with %d vertices and %d edges)' % (len(self.V),len(self.E)) def add_vertices(self,vertex_list): ''' This method will add the vertices in the vertex_list to the set of vertices for this graph. Since V is a set, duplicate vertices will not be added to V. ''' for v in vertex_list: self.V.add(v) self.build_Adj() def add_edges(self,edge_list): ''' This method will add a list of edges to the graph It will insure that the vertices of each edge are included in the set of vertices (and not duplicated). It will also insure that edges are added to the list of edges and not duplicated. ''' for s,t in edge_list: if (s,t) not in self.E and (t,s) not in self.E: self.V.add(s) self.V.add(t) self.E.add((s,t)) self.build_Adj() def build_Adj(self): self.Adj = {} for v in self.V: self.Adj[v] = [] for e in self.E: s,t = e self.Adj[s].append(t) self.Adj[t].append(s) def Degree(self,v): return len(self.Adj[v]) def plot(self,Vc): # Vc is a dictionary with the coordinates for each vertex g = Graphics() # Create the list of coordinates Vcoords = [Vc[v] for v in self.V] # Include the vertices as red dots g += point2d(Vcoords,rgbcolor=(1,0,0),size=25) # Include the names of the vertices for v in self.V: g += text(v,(1.01*Vc[v][0], 1.005*Vc[v][1])) # Include the edges for edge in self.E: u,v = edge g += line([Vc[u],Vc[v]]) return g def build_Components(self): Visited = {} for v in self.V: Visited[v] = False components = [] Q = Queue() for v0 in self.V: if not Visited[v0]: comp = [] Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() comp.append(v) for v in self.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) components.append(comp) return components def is_connected(self): Visited = {} for v in self.V: Visited[v] = False Q = Queue() for v0 in self.V: if not Visited[v0]: Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() for v in self.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) break for v in self.V: if not Visited[v]: # The Graph is not connected return False # The Graph is connected return True 
       

A Queue Class

The following block defines a queue class with five methods - enqueue, dequeue, peek, clear, and display. However, instead of following the Stack class approach and having this own a private deque object, this queue is a subclass of the deque class. So this queue object is a deque. One consequence is that this queue object will inherit the methods of the deque class, which includes the clear method. This can be confirmed with the tab completion in the block following the definition of the Queue class.

import collections ''' This block defines a Queue class as a subclass of the collections.deque class This class inherits all the methods of the deque class and adds the methods enqueue, dequeue, peek, and display. Daniel D. Warner February 26, 2012 ''' class Queue(collections.deque): def enqueue(self,x): ''' enqueue adds an item to the end of the queue.''' self.appendleft(x) def dequeue(self): ''' dequeue removes an item from the front of the queue.''' if 0 < len(self): return self.pop() else: return None def peek(self): if 0 < len(self): p = self.pop() self.append(p) return p else: return None def display(self): print self 
       

A Priority Queue Class

A priority queue is a container where each item is inserted with a certain priority.  When an item is removed, the item with the highest priority is the item that is removed.  Priority queues can be implemented using a heap.  A heap is a Complete Binary Tree with a partial ordering.  A complete binary tree is a binary tree where the tree is filled out  from top to bottom, left to right.  To be a heap, the complete binary tree must satisfy the following partial ordering criteria.

The priority of the parent must always be equal to or higher than the priority of its children.  

This is often referred to as the heap property.  The heap property is an invariant which must be true before and after pushing or popping an item.

There is a natural embedding of a complete binary tree into an array using the functions

  • parent(n) = (n-1)//2
  • leftchild(n) = 2*n + 1
  • rightchild(n) = 2*n + 2

The following version of the Priority Queue makes the bubble-up and sift-down routines explicit, so that it is possible to extend the class to allow for changes in the priority and other features that are important for discrete event simulation.

This class has been extended to include the routines priority_of(object)  and adjust(new_priority, object). These extensions are necessary for the efficient implementation of Dijkstra's algorithm.

class PriorityQueue(): ''' The arguments passed to a PriorityQueue must consist of a priority and an object. It must be possible to compare priorities using the < operator. By adding the dictionary indx, it is possible to change the priority of an object in the priority queue. ''' def __init__(self): self._pq = [] self._indx = {} def _parent(self,n): return (n-1)//2 def _leftchild(self,n): return 2*n + 1 def _rightchild(self,n): return 2*n + 2 def push(self, pri, obj): self._pq.append((pri,obj)) n = len(self._pq) self._indx[obj] = n-1 self._bubble_up(n-1) # print 'push pq',self._pq # print 'push index',self._indx def _bubble_up(self,c): while 0<c: c_item = self._pq[c] p = self._parent(c) p_item = self._pq[p] if c_item < p_item: self._pq[p] = c_item self._pq[c] = p_item c_obj = c_item[1] p_obj = p_item[1] self._indx[c_obj] = p self._indx[p_obj] = c c = p else: break def pop(self): n = len(self._pq) if 0==n: obj = None elif 1==n: pri,obj = self._pq.pop() self._indx[obj] = None else: pri,obj = self._pq[0] self._indx[obj] = None self._pq[0] = self._pq.pop() pri1,obj1 = self._pq[0] self._indx[obj1] = 0 self._sift_down(0) # print 'pop pq',self._pq # print 'pop index',self._indx return pri,obj def _sift_down(self,p): n = len(self._pq) while p<n: p_item = self._pq[p] lc = self._leftchild(p) if n <= lc: break c_item = self._pq[lc] c = lc rc = self._rightchild(p) if rc < n: r_item = self._pq[rc] if r_item < c_item: c_item = r_item c = rc if p_item <= c_item: break self._pq[p] = c_item self._pq[c] = p_item c_obj = c_item[1] p_obj = p_item[1] self._indx[c_obj] = p self._indx[p_obj] = c p = c def priority_of(self,obj): if obj in self._indx.keys(): i = self._indx[obj] if not i == None: pri,obj = self._pq[i] return pri return None def adjust(self, new_pri, obj): if obj in self._indx: i = self._indx[obj] item = self._pq[i] old_pri = item[0] self._pq[i] = (new_pri,obj) if new_pri < old_pri: self._bubble_up(i) else: self._sift_down(i) else: self.push(new_pri,obj) def is_not_empty(self): if 0 < len(self._pq): return True else: return False 
       

Create a  Graph, G2, then add weights to make it a Network.  Finally display the Network.

# Build a simple example V = ['A', 'B', 'C', 'D', 'E', 'F'] Vcoord = {'A':(5,80),'B':(20,40),'C':(5,-80),'D':(20,-40),'E':(12,10),'F':(-20,10)} E2 = [('A','B'),('A','E'),('A','F'),('B','D'),('C','D'),('C','E'),('C','F')] G2 = Graph(V,E2) print 'G2.V',G2.V print 'G2.E',G2.E print 'G2.Adj',G2.Adj g2 = G2.plot(Vcoord) show(g2,figsize=(3,3),axes=False) print 'Degrees' for v in V: print v,G2.Degree(v) print G2.build_Components() if G2.is_connected(): print 'G2 is connected' else: print 'G2 is NOT connected' 
       
(Initializing a graph with 6 vertices and 7 edges)
G2.V set(['A', 'C', 'B', 'E', 'D', 'F'])
G2.E set([('C', 'F'), ('C', 'D'), ('A', 'F'), ('A', 'E'), ('A', 'B'),
('C', 'E'), ('B', 'D')])
G2.Adj {'A': ['F', 'E', 'B'], 'C': ['F', 'D', 'E'], 'B': ['A', 'D'],
'E': ['A', 'C'], 'D': ['C', 'B'], 'F': ['C', 'A']}

Degrees
A 3
B 2
C 3
D 2
E 2
F 2
[['F', 'B', 'A', 'C', 'D', 'E']]
G2 is connected
(Initializing a graph with 6 vertices and 7 edges)
G2.V set(['A', 'C', 'B', 'E', 'D', 'F'])
G2.E set([('C', 'F'), ('C', 'D'), ('A', 'F'), ('A', 'E'), ('A', 'B'), ('C', 'E'), ('B', 'D')])
G2.Adj {'A': ['F', 'E', 'B'], 'C': ['F', 'D', 'E'], 'B': ['A', 'D'], 'E': ['A', 'C'], 'D': ['C', 'B'], 'F': ['C', 'A']}

Degrees
A 3
B 2
C 3
D 2
E 2
F 2
[['F', 'B', 'A', 'C', 'D', 'E']]
G2 is connected
W = {('A','B'):7, ('A','E'):18, ('A','F'):19, ('B','D'):14, ('C','D'):13, ('C','E'):16, ('C','F'):21} for edge in W.keys(): s,t = edge w = W[edge] W[(t,s)] = w for edge in G2.E: s,t = edge w = W[(s,t)] xs,ys = Vcoord[s] xt,yt = Vcoord[t] xw,yw = ((xs+xt)/2,1/2+(ys+yt)/2) g2 += text(w,(1.1*xw,1.1*yw)) show(g2,figsize=(3,3),axes=False) 
       

Shortest Paths

We will start by looking at 3 algorihtms for finding the shortest path between two vertices in a network.  The two networks will be G2 and Atlas from the previous examples.

For G2 we will find the shortest paths from A to B, A to C, and A to D.

For Atlas we will find the shortest paths from Wilmington, NC to Memphis, TN; from Daytona Beach, FL to Lexington, KY; and from Charleston, SC to Charleston, WV.

The first algorithm is a depth-first, recursive, back-tracking search.  Once a vertex has been added to the path it is no longer available.  We will use a dictionary labeled, available, rather than a linear search to see if the vertex in already in the path.  After we have found one path to the last vertex, we can prune all future branches of the search tree. 

def Shortest_Path_df(G,W,path,available,last_v,distance,best,counts): counts[0] += 1 # Number of vertices visited counts[1] = max(counts[1],len(path)) # Maximum path examined current = path[-1] if current == last_v: # Found a path ## print path,distance if distance < best[1]: best[0] = copy(path) best[1] = distance else: for v in G.Adj[current]: if available[v]: w = W[(current,v)] if distance+w < best[1]: path.append(v) available[v] = False best,counts = Shortest_Path_df(G,W,path,available,last_v,distance+w,best,counts) path.pop() available[v] = True return best,counts def Shortest_Path_DF(G,W,first_v,last_v): available = {} for v in G.V: available[v] = True available[first_v] = False best = [[first_v],infinity] return Shortest_Path_df(G,W,[first_v],available,last_v,0,best,[0,0]) 
       
best,counts = Shortest_Path_DF(G2,W,'A','B') print 'Shortest Path:',best[0] print 'Length:',best[1] print 'Cities examined:',counts[0],'Longest Path:',counts[1] timeit("Shortest_Path_DF(G2,W,'A','B')") 
       
Shortest Path: ['A', 'B']
Length: 7
Cities examined: 12 Longest Path: 5
625 loops, best of 3: 99.3 µs per loop
Shortest Path: ['A', 'B']
Length: 7
Cities examined: 12 Longest Path: 5
625 loops, best of 3: 99.3 µs per loop
best,counts = Shortest_Path_DF(G2,W,'A','C') print 'Shortest Path:',best[0] print 'Length:',best[1] print 'Cities examined:',counts[0],'Longest Path:',counts[1] timeit("Shortest_Path_DF(G2,W,'A','C')") 
       
Shortest Path: ['A', 'E', 'C']
Length: 34
Cities examined: 7 Longest Path: 3
625 loops, best of 3: 61.3 µs per loop
Shortest Path: ['A', 'E', 'C']
Length: 34
Cities examined: 7 Longest Path: 3
625 loops, best of 3: 61.3 µs per loop
best,counts = Shortest_Path_DF(G2,W,'A','D') print 'Shortest Path:',best[0] print 'Length:',best[1] print 'Cities examined:',counts[0],'Longest Path:',counts[1] timeit("Shortest_Path_DF(G2,W,'A','D')") 
       
Shortest Path: ['A', 'B', 'D']
Length: 21
Cities examined: 9 Longest Path: 4
625 loops, best of 3: 79.8 µs per loop
Shortest Path: ['A', 'B', 'D']
Length: 21
Cities examined: 9 Longest Path: 4
625 loops, best of 3: 79.8 µs per loop

The Breadth-First Search uses a queue that stores tuples consisting of a path and the distance.

Note that if the distance between every adjacent vertex was the same then the breadth-first search could stop as soon as it found the last vertex.  However, since this isn't the case we must keep searching as long as there are candidates. It is also the case that since there are many different paths in the queue, checking for availability requires a linear search to see if the vertex is in the path.

def Shortest_Path_BF(G,W,first_v,last_v): best = [[first_v],infinity] Q = Queue() Q.enqueue(([first_v],0)) q_size = 1 max_q = q_size # Each item in the queue is a (path,distance) tuple while 0<len(Q): path,distance = Q.dequeue() q_size -= len(path) if distance < best[1]: # This path is still a contender current = path[-1] for v in G.Adj[current]: if not v in path: new_distance = distance + W[(current,v)] if new_distance < best[1]: new_path = copy(path) new_path.append(v) if v == last_v: # Found a path best[0] = copy(new_path) best[1] = new_distance ## print new_path,'\tdistance:',best[1],'\tmax queue',max_q else: Q.enqueue((new_path,new_distance)) q_size += len(new_path) max_q = max(max_q,q_size) return best,max_q 
       
best,max_q = Shortest_Path_BF(G2,W,'A','B') print 'Shortest Path:',best[0] print 'Length:',best[1] print 'Max Queue size:',max_q timeit("Shortest_Path_BF(G2,W,'A','B')") 
       
Shortest Path: ['A', 'B']
Length: 7
Max Queue size: 6
625 loops, best of 3: 74.5 µs per loop
Shortest Path: ['A', 'B']
Length: 7
Max Queue size: 6
625 loops, best of 3: 74.5 µs per loop
best,max_q = Shortest_Path_BF(G2,W,'A','C') print 'Shortest Path:',best[0] print 'Length:',best[1] print 'Max Queue size:',max_q timeit("Shortest_Path_BF(G2,W,'A','C')") 
       
Shortest Path: ['A', 'E', 'C']
Length: 34
Max Queue size: 9
625 loops, best of 3: 129 µs per loop
Shortest Path: ['A', 'E', 'C']
Length: 34
Max Queue size: 9
625 loops, best of 3: 129 µs per loop
best,max_q = Shortest_Path_BF(G2,W,'A','D') print 'Shortest Path:',best[0] print 'Length:',best[1] print 'Max Queue size:',max_q timeit("Shortest_Path_BF(G2,W,'A','D')") 
       
Shortest Path: ['A', 'B', 'D']
Length: 21
Max Queue size: 9
625 loops, best of 3: 166 µs per loop
Shortest Path: ['A', 'B', 'D']
Length: 21
Max Queue size: 9
625 loops, best of 3: 166 µs per loop

An Atlas Example

The following blocks define an Atlas of 32 cities in the Southeast.  

# Index City State Latitude Longitude southeast_cities = """ 1 Atlanta GA 33.4500 84.2300 2 Augusta GA 33.2800 82.0200 3 Tifton GA 31.2700 83.3100 4 Montgomery AL 32.3000 86.4000 5 Birmingham AL 33.5670 86.7500 6 Chattanooga TN 35.0330 85.2000 7 Savannah GA 32.1330 81.2000 8 Columbia SC 33.9500 81.1170 9 Charlotte NC 35.2200 80.9300 10 Asheville NC 34.4300 82.5500 11 Knoxville TN 35.8200 83.9800 12 Charleston SC 32.9000 80.0300 13 Jacksonville FL 30.5000 81.7000 14 Tallahassee FL 30.3830 84.3670 15 Mobile AL 30.6830 88.2500 16 Meridian MS 32.3330 88.7500 17 Columbus MS 33.6345 88.4498 18 Huntsville AL 34.7793 86.6124 19 Corinth MS 34.9314 88.5235 20 Memphis TN 35.1056 90.0070 21 Nashville TN 36.1658 86.7844 22 Florence SC 34.1953 79.7628 23 Raleigh NC 35.7719 78.6389 24 Bluefield WV 37.2697 81.2225 25 Greensboro NC 36.0830 79.9500 26 Wilmington NC 34.2670 77.9170 27 Roanoke VA 37.3170 79.9670 28 Charleston WV 38.3670 81.6000 29 Lexington KY 38.0500 85.0000 30 Myrtle_Beach SC 33.6800 78.9300 31 Daytona_Beach FL 29.1800 81.0500 32 Gainsville FL 29.6800 82.2700 """ 
       
# Edge List (source target distance) road_map = """ Atlanta GA Augusta GA 151 Atlanta GA Tifton GA 182 Atlanta GA Montgomery AL 167 Atlanta GA Birmingham AL 148 Atlanta GA Chattanooga TN 115 Atlanta GA Savannah GA 252 Atlanta GA Columbia SC 213 Atlanta GA Charlotte NC 240 Atlanta GA Asheville NC 206 Atlanta GA Knoxville TN 215 Augusta GA Tifton GA 203 Augusta GA Savannah GA 128 Augusta GA Columbia SC 68 Augusta GA Asheville NC 217 Augusta GA Charleston SC 175 Tifton GA Montgomery AL 207 Tifton GA Birmingham AL 326 Tifton GA Jacksonville FL 166 Tifton GA Tallahassee FL 90 Tifton GA Gainsville FL 151 Montgomery AL Tallahassee FL 214 Montgomery AL Mobile AL 170 Montgomery AL Meridian MS 152 Montgomery AL Columbus MS 197 Birmingham AL Chattanooga TN 143 Birmingham AL Mobile AL 262 Birmingham AL Meridian MS 146 Birmingham AL Columbus MS 118 Birmingham AL Huntsville AL 99 Birmingham AL Corinth MS 223 Birmingham AL Memphis TN 247 Chattanooga TN Asheville NC 227 Chattanooga TN Knoxville TN 114 Chattanooga TN Huntsville AL 106 Chattanooga TN Nashville TN 128 Savannah GA Columbia SC 155 Savannah GA Charleston SC 105 Savannah GA Jacksonville FL 140 Savannah GA Tallahassee FL 299 Savannah GA Florence SC 172 Columbia SC Charlotte NC 91 Columbia SC Asheville NC 157 Columbia SC Charleston SC 112 Columbia SC Florence SC 79 Columbia SC Raleigh NC 228 Columbia SC Bluefield WV 261 Charlotte NC Asheville NC 125 Charlotte NC Raleigh NC 168 Charlotte NC Greensboro NC 97 Charlotte NC Wilmington NC 204 Asheville NC Knoxville TN 115 Asheville NC Bluefield WV 233 Asheville NC Greensboro NC 170 Asheville NC Roanoke VA 254 Knoxville TN Nashville TN 178 Knoxville TN Roanoke VA 257 Knoxville TN Charleston WV 314 Knoxville TN Lexington KY 173 Charleston SC Myrtle_Beach SC 97 Jacksonville FL Tallahassee FL 163 Jacksonville FL Daytona_Beach FL 90 Jacksonville FL Gainsville FL 73 Tallahassee FL Mobile AL 240 Tallahassee FL Gainsville FL 149 Huntsville AL Corinth MS 126 Corinth MS Memphis TN 93 Memphis TN Nashville TN 210 """ 
       
import re # Build the vertex_list and the vcoords p = re.compile(r'\s+(\d+)\s+(\w+)\s+(\w+)\s+(\d+\.\d+)\s+(\d+\.\d+)') vertex_list = [] vcoords = {} pos = 0 while pos<len(southeast_cities): m = p.search(southeast_cities,pos) if m: #print m.group() g = m.groups() if g[0] and g[1] and g[2] and g[3] and g[4]: city = g[1]+', '+g[2] vertex_list.append(city) coord = (float(g[3]),float(g[4])) vcoords[city] = coord pos = m.end() else: break for v in vertex_list: c = vcoords[v] if 14 < len(v): print v,'\t(', c[0],',',c[1],')' else: print v,'\t\t(', c[0],',',c[1],')' 
       
Atlanta, GA 		( 33.45 , 84.23 )
Augusta, GA 		( 33.28 , 82.02 )
Tifton, GA 		( 31.27 , 83.31 )
Montgomery, AL 		( 32.3 , 86.4 )
Birmingham, AL 		( 33.567 , 86.75 )
Chattanooga, TN 	( 35.033 , 85.2 )
Savannah, GA 		( 32.133 , 81.2 )
Columbia, SC 		( 33.95 , 81.117 )
Charlotte, NC 		( 35.22 , 80.93 )
Asheville, NC 		( 34.43 , 82.55 )
Knoxville, TN 		( 35.82 , 83.98 )
Charleston, SC 		( 32.9 , 80.03 )
Jacksonville, FL 	( 30.5 , 81.7 )
Tallahassee, FL 	( 30.383 , 84.367 )
Mobile, AL 		( 30.683 , 88.25 )
Meridian, MS 		( 32.333 , 88.75 )
Columbus, MS 		( 33.6345 , 88.4498 )
Huntsville, AL 		( 34.7793 , 86.6124 )
Corinth, MS 		( 34.9314 , 88.5235 )
Memphis, TN 		( 35.1056 , 90.007 )
Nashville, TN 		( 36.1658 , 86.7844 )
Florence, SC 		( 34.1953 , 79.7628 )
Raleigh, NC 		( 35.7719 , 78.6389 )
Bluefield, WV 		( 37.2697 , 81.2225 )
Greensboro, NC 		( 36.083 , 79.95 )
Wilmington, NC 		( 34.267 , 77.917 )
Roanoke, VA 		( 37.317 , 79.967 )
Charleston, WV 		( 38.367 , 81.6 )
Lexington, KY 		( 38.05 , 85.0 )
Myrtle_Beach, SC 	( 33.68 , 78.93 )
Daytona_Beach, FL 	( 29.18 , 81.05 )
Gainsville, FL 		( 29.68 , 82.27 )
Atlanta, GA 		( 33.45 , 84.23 )
Augusta, GA 		( 33.28 , 82.02 )
Tifton, GA 		( 31.27 , 83.31 )
Montgomery, AL 		( 32.3 , 86.4 )
Birmingham, AL 		( 33.567 , 86.75 )
Chattanooga, TN 	( 35.033 , 85.2 )
Savannah, GA 		( 32.133 , 81.2 )
Columbia, SC 		( 33.95 , 81.117 )
Charlotte, NC 		( 35.22 , 80.93 )
Asheville, NC 		( 34.43 , 82.55 )
Knoxville, TN 		( 35.82 , 83.98 )
Charleston, SC 		( 32.9 , 80.03 )
Jacksonville, FL 	( 30.5 , 81.7 )
Tallahassee, FL 	( 30.383 , 84.367 )
Mobile, AL 		( 30.683 , 88.25 )
Meridian, MS 		( 32.333 , 88.75 )
Columbus, MS 		( 33.6345 , 88.4498 )
Huntsville, AL 		( 34.7793 , 86.6124 )
Corinth, MS 		( 34.9314 , 88.5235 )
Memphis, TN 		( 35.1056 , 90.007 )
Nashville, TN 		( 36.1658 , 86.7844 )
Florence, SC 		( 34.1953 , 79.7628 )
Raleigh, NC 		( 35.7719 , 78.6389 )
Bluefield, WV 		( 37.2697 , 81.2225 )
Greensboro, NC 		( 36.083 , 79.95 )
Wilmington, NC 		( 34.267 , 77.917 )
Roanoke, VA 		( 37.317 , 79.967 )
Charleston, WV 		( 38.367 , 81.6 )
Lexington, KY 		( 38.05 , 85.0 )
Myrtle_Beach, SC 	( 33.68 , 78.93 )
Daytona_Beach, FL 	( 29.18 , 81.05 )
Gainsville, FL 		( 29.68 , 82.27 )
# Build the edge_list and the list of weights q = re.compile(r'\s+(\w+)\s+(\w+)\s+(\w+)\s+(\w+)\s+(\d+)') edge_list = [] weights = {} pos = 0 while pos<len(road_map): m = q.search(road_map,pos) if m: # print m.group() g = m.groups() if g[0] and g[1] and g[2] and g[3] and g[4]: s = g[0]+', '+g[1] t = g[2]+', '+g[3] w = int(g[4]) edge_list.append((s,t)) weights[(s,t)] = w weights[(t,s)] = w pos = m.end() else: break 
       
Atlas = Graph(vertex_list, edge_list) g = Atlas.plot(vcoords) for edge in Atlas.E: s,t = edge w = weights[(s,t)] xs,ys = vcoords[s] xt,yt = vcoords[t] xw,yw = ((xs+xt)/2,(ys+yt)/2) g += text(w,(xw,yw)) #show(G2plot,figsize=(10,10),axes=False) show(g,figsize=(10,8),axes=False) 
       
(Initializing a graph with 32 vertices and 67 edges)
(Initializing a graph with 32 vertices and 67 edges)

Best-First Shortest Path Algorithm

This is a heuristic algorithm for finding the shortest path in a weighted graph.  It assumes that you have available a function which provides an underestimate of the best possible result. In the case of the Atlas, a natural candidate is the length of the path from the origin to the current city plus the straight line ("as the crow flies") distance from the current city to the destination. We start the algorithm with an empty path and a best distance of infinity. Then set the current city to origin.

Given a candidate path and the current city (the last city in the candidate path) we then look at the current city's neighbors. For each neighbor that is not already in the candidate path we compute the heuristic distance estimate, which is the distance along the candidate path, plus the distance from the current city to the neighbor, plus the straightline distance from the neighbor to the destination. If this heuristic distance estimate is less than the distance of the best path found so far, we append the neighbor to a copy of the candidate path and place this path along with the heuristic distance in the priority queue.

When all the neighbors have been examined, we pop the path with the shortest heuristic distance estimate from the priority queue. That path becomes the new candidate path and the last city in that path becomes the current city. Whenever the current city is the destination, we update the "best path" and its distance. We can terminate the search as soon as the heuristic distance estimate for the next path in the priority queue is larger than the actual distance of the "best path".  

# Write a function that uses a best-first search strategy
# to find the shortest route between two cities in Atla

 

The following function computes the straight-line distance between two cities.  The block also verifies that the calculation and the specified distances are consistent.

def crow_fly(network, vcoords, city1, city2): lat1,long1 = vcoords[city1] lat2,long2 = vcoords[city2] # One minute of longitude at the equator is a geographical mile # equal to 6087.025 feet # However the road map distance are US miles equal to 5280 feet # So the conversion factor at the equator should be # 6087.025/5280 approximately 1.1528456 # However, we are signigicantly north of the equator and the heuristic # requires an underestimate, so we use the smaller conversion factor yd = (lat2 - lat1)*60*(0.86) xd = (long2 - long1)*60*(0.86) return sqrt(xd^2 + yd^2) # Check consistency of the atlas distances and the lat-long conversion print 'Checking consistency.' AOK = True #edges = Atlas.get_edges() for edge in Atlas.E: s,t = edge d1 = crow_fly(Atlas, vcoords, s, t) d2 = weights[edge] if d2 < d1: print 'Inconsistent',s,t,d1,d2 AOK = False if AOK: print 'The crow-fly heuristic is consistent.' 
       
Checking consistency.
The crow-fly heuristic is consistent.
Checking consistency.
The crow-fly heuristic is consistent.

The following function finds the shortest path between two cities using a best-first search.

def Shortest_Path_Best(network, weights, start_city, destination): counts = [0,0,0] # [number of cities examined, number of paths found, maximum queue size] best = [[],infinity] # best path and best length path = (start_city,) PQ = PriorityQueue() d0 = crow_fly(network,vcoords,start_city,destination) pt = (path,0) PQ.push(d0,pt) q_size = len(path) max_q = q_size #print PQ._pq while PQ.is_not_empty(): pri,(path,length) = PQ.pop() q_size -= len(path) #print pri,path,length current = list(path)[-1] counts[0] += 1 if current == destination: # We have found a path counts[1] += 1 if length <= best[1]: best = [path, length] # print counts,best elif pri <= best[1]: neighbors = network.Adj[current] for city in neighbors: if city not in path: # Inefficient in time but not space w = weights[(current,city)] new_length = length + w new_pri = crow_fly(network,vcoords,city,destination)+new_length if (new_pri <= best[1]): new_path = copy(path) p_list = list(new_path) p_list.append(city) new_path = tuple(p_list) q_size += len(new_path) max_q = max(max_q,q_size) PQ.push(new_pri,(new_path,new_length)) else: pass counts[2] = max_q return best,counts 
       

The following code uses the three algorithms to find the shortest route from Wilmington, NC to Memphis, TN.

print "Depth-First" best,counts = Shortest_Path_DF(Atlas,weights,'Wilmington, NC', 'Memphis, TN') print best[0] print 'Length:',best[1] print 'Cities examined:',counts[0],'Longest Path:',counts[1] timeit("Shortest_Path_DF(Atlas,weights,'Wilmington, NC', 'Memphis, TN')") print "\nBreadth-First" best,max_q = Shortest_Path_BF(Atlas,weights,'Wilmington, NC', 'Memphis, TN') print best[0] print 'Length:',best[1] print 'Max Queue size:',max_q timeit("Shortest_Path_BF(Atlas,weights,'Wilmington, NC', 'Memphis, TN')") print "\nBest-First" best,counts = Shortest_Path_Best(Atlas, weights, 'Wilmington, NC', 'Memphis, TN') path = best[0] length = best[1] print path print length, counts timeit("Shortest_Path_Best(Atlas, weights, 'Wilmington, NC', 'Memphis, TN')") 
       
Depth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN']
Length: 832
Cities examined: 1333 Longest Path: 13
125 loops, best of 3: 6.89 ms per loop

Breadth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN']
Length: 832
Max Queue size: 1183
125 loops, best of 3: 6.98 ms per loop

Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]
25 loops, best of 3: 9.51 ms per loop
Depth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN']
Length: 832
Cities examined: 1333 Longest Path: 13
125 loops, best of 3: 6.89 ms per loop

Breadth-First
['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN']
Length: 832
Max Queue size: 1183
125 loops, best of 3: 6.98 ms per loop

Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]
25 loops, best of 3: 9.51 ms per loop

Exercise 1:  Using the three algorithms find the shortest route from Daytona Beach, FL to Lexington, KY.

# Find the shortest routes 
# from Wilmington, NC to Memphis, TN
# from Daytona_Beach, FL to Lexington, KY
# from Charleston, SC to Charleston, WV
print "Depth-First" best,counts = Shortest_Path_DF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY') print best[0] print 'Length:',best[1] print 'Cities examined:',counts[0],'Longest Path:',counts[1] timeit("Shortest_Path_DF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY')") print "\nBreadth-First" best,max_q = Shortest_Path_BF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY') print best[0] print 'Length:',best[1] print 'Max Queue size:',max_q timeit("Shortest_Path_BF(Atlas,weights,'Daytona_Beach, FL', 'Lexington, KY')") print "\nBest-First" best,counts = Shortest_Path_Best(Atlas, weights, 'Daytona_Beach, FL', 'Lexington, KY') path = best[0] length = best[1] print path print length, counts timeit("Shortest_Path_Best(Atlas, weights, 'Daytona_Beach, FL', 'Lexington, KY')") 
       
Depth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY']
Length: 826
Cities examined: 2612 Longest Path: 25
25 loops, best of 3: 23.3 ms per loop

Breadth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY']
Length: 826
Max Queue size: 2202
25 loops, best of 3: 12.5 ms per loop

Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]
25 loops, best of 3: 33.6 ms per loop
Depth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY']
Length: 826
Cities examined: 2612 Longest Path: 25
25 loops, best of 3: 23.3 ms per loop

Breadth-First
['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY']
Length: 826
Max Queue size: 2202
25 loops, best of 3: 12.5 ms per loop

Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]
25 loops, best of 3: 33.6 ms per loop

Exercise 2:  Using the three algorithms find the shortest route from Charleston, SC to Charleston, WV.  

Then summarize the performance of each algorithm and list each algorithms strengths.

print "Depth-First" best,counts = Shortest_Path_DF(Atlas,weights,'Charleston, SC', 'Charleston, WV') print best[0] print 'Length:',best[1] print 'Cities examined:',counts[0],'Longest Path:',counts[1] timeit("Shortest_Path_DF(Atlas,weights,'Charleston, SC', 'Charleston, WV')") print "\nBreadth-First" best,max_q = Shortest_Path_BF(Atlas,weights,'Charleston, SC', 'Charleston, WV') print best[0] print 'Length:',best[1] print 'Max Queue size:',max_q timeit("Shortest_Path_BF(Atlas,weights,'Charleston, SC', 'Charleston, WV')") print "\nBest-First" best,counts = Shortest_Path_Best(Atlas, weights, 'Charleston, SC', 'Charleston, WV') path = best[0] length = best[1] print path print length, counts timeit("Shortest_Path_Best(Atlas, weights, 'Charleston, SC', 'Charleston, WV')") 
       
Depth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV']
Length: 698
Cities examined: 199772 Longest Path: 25
5 loops, best of 3: 2.73 s per loop

Breadth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV']
Length: 698
Max Queue size: 1940
25 loops, best of 3: 11 ms per loop

Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV')
698 [323, 5, 1212]
25 loops, best of 3: 39.6 ms per loop
Depth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV']
Length: 698
Cities examined: 199772 Longest Path: 25
5 loops, best of 3: 2.73 s per loop

Breadth-First
['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV']
Length: 698
Max Queue size: 1940
25 loops, best of 3: 11 ms per loop

Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV')
698 [323, 5, 1212]
25 loops, best of 3: 39.6 ms per loop
#It looks like the 'Best-First' algorithm will run in pretty average time no matter what the input is, and the breadth-first and depth-first #change depending on the starting point and ending point. #It seems like the breadth-first search is stronger when the two points are closer together, and the depth-first search is stronger when the #points are farther apart from each other. 
       

Exercise 3.  Complete the definition of the function for displaying the shortest path between two of the cities in Atlas, plotted in red on top of a copy of original display of the Atlas. Also print out the total distance for this path.

def display_path(G,W,path): g1 = copy(g) w_sum = 0 u = path[0] for k in range(1,len(path)): v = path[k] g1 += line([vcoords[u],vcoords[v]], color='red') u = path[k] w_sum += 1 show(g1,figsize=[10,8],axes=False) print 'Path length:',w_sum 
       

Using the Shortest_Path_Best routine, find the shortest route from Wilmington, NC to Memphis, TN.

Then print out the search statistics and display the path.

print "\nBest-First" best,counts = Shortest_Path_Best(Atlas, weights, 'Wilmington, NC', 'Memphis, TN') path = best[0] length = best[1] print path print length, counts display_path(Atlas,weights,path) 
       
Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN',
'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]

Path length: 5
Best-First
('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN')
832 [84, 2, 332]

Path length: 5

Exercise 4.  Using the Shortest_Path_Best routine, find the shortest route from Daytona_Beach, FL to Lexington, KY.

Then print out the search statistics and display the path.

print "\nBest-First" best,counts = Shortest_Path_Best(Atlas, weights, 'Daytona_Beach, FL', 'Lexington, KY') path = best[0] length = best[1] print path print length, counts display_path(Atlas,weights,path) 
       
Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA',
'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]

Path length: 5
Best-First
('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY')
826 [280, 6, 1377]

Path length: 5

Exercise 5. Using the preceeding Shortest_Path_Best routine, find the shortest route from Charleston, SC to Charleston, WV.

Then print out the search statistics and display the path.

print "\nBest-First" best,counts = Shortest_Path_Best(Atlas, weights, 'Charleston, SC', 'Charleston, WV') path = best[0] length = best[1] print path print length, counts display_path(Atlas,weights,path) 
       
Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN',
'Charleston, WV')
698 [323, 5, 1212]

Path length: 4
Best-First
('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV')
698 [323, 5, 1212]

Path length: 4

The Floyd-Warshall Algorithm

The Floyd-Warshall algorithm calculates the shortest distance between every pair of cities. We start with a 2D array, FW. 

We initialize FW to

\[
{\bf{FW}}(i,j,-1) = \left\{ {\begin{array}{*{20}c}
   {EdgeCost(i,j)}  \\
   {\infty {\rm{  otherwise}}}  \\
\end{array}} \right.
\]

Then for $k=0\ldots nV-1$

\[
{\bf{FW}}(i,j,k) = min({\bf{FW}}(i,j,k - 1),{\bf{FW}}(i,k,k - 1) + {\bf{FW}}(k,j,k - 1))
\]

 

# First build the dictionary that provides the index of each city Atlas_vindex = {} for k,v in enumerate(Atlas.V): Atlas_vindex[v] = k print Atlas_vindex inf = 0 for edge in Atlas.E: inf += weights[edge] print inf 
       
{'Charlotte, NC': 0, 'Raleigh, NC': 1, 'Florence, SC': 2, 'Meridian,
MS': 3, 'Chattanooga, TN': 4, 'Augusta, GA': 5, 'Jacksonville, FL': 25,
'Columbia, SC': 13, 'Tifton, GA': 8, 'Knoxville, TN': 9, 'Tallahassee,
FL': 10, 'Roanoke, VA': 11, 'Huntsville, AL': 12, 'Corinth, MS': 7,
'Atlanta, GA': 14, 'Mobile, AL': 15, 'Charleston, WV': 16, 'Nashville,
TN': 17, 'Birmingham, AL': 30, 'Montgomery, AL': 19, 'Asheville, NC':
20, 'Memphis, TN': 21, 'Charleston, SC': 22, 'Bluefield, WV': 23,
'Savannah, GA': 24, 'Myrtle_Beach, SC': 6, 'Gainsville, FL': 26,
'Columbus, MS': 27, 'Wilmington, NC': 28, 'Lexington, KY': 29,
'Greensboro, NC': 18, 'Daytona_Beach, FL': 31}
11494
{'Charlotte, NC': 0, 'Raleigh, NC': 1, 'Florence, SC': 2, 'Meridian, MS': 3, 'Chattanooga, TN': 4, 'Augusta, GA': 5, 'Jacksonville, FL': 25, 'Columbia, SC': 13, 'Tifton, GA': 8, 'Knoxville, TN': 9, 'Tallahassee, FL': 10, 'Roanoke, VA': 11, 'Huntsville, AL': 12, 'Corinth, MS': 7, 'Atlanta, GA': 14, 'Mobile, AL': 15, 'Charleston, WV': 16, 'Nashville, TN': 17, 'Birmingham, AL': 30, 'Montgomery, AL': 19, 'Asheville, NC': 20, 'Memphis, TN': 21, 'Charleston, SC': 22, 'Bluefield, WV': 23, 'Savannah, GA': 24, 'Myrtle_Beach, SC': 6, 'Gainsville, FL': 26, 'Columbus, MS': 27, 'Wilmington, NC': 28, 'Lexington, KY': 29, 'Greensboro, NC': 18, 'Daytona_Beach, FL': 31}
11494

The following code, build_Floyd_Warshall, Floyd-Warshall algorithm that creates the matrix of shortest distances between every pair of cities.

def build_Floyd_Warshall(G,Vindex,W): nV = len(G.V) # Build the nV-by-nV matrix and set the diagonal entries # to zero, and set the off-diagonal entries to infinity, FW = matrix(ZZ,nV) for i in range(nV): for j in range(nV): if i==j: FW[i,j] = 0 else: FW[i,j] = inf # print FW.str() # Now for each edge, (s,t), set the corresponding # entries in the matrix to the given weights for edge in G.E: w = weights[edge] s,t = edge sk = Vindex[s] tk = Vindex[t] FW[sk,tk] = w FW[tk,sk] = w # The FW matrix has been initialized so that immediate distances # are recorded and all other distances are initialized to infinity # Use the Floyd-Warshall algorithm to calculate the 2D array of the # shortest distance between every pair of cities. nV = len(G.V) for k in range(1,nV): for i in range(nV): for j in range(i+1,nV): fkij = min(FW[i,j], FW[i,k-1]+FW[k-1,j]) FW[i,j] = fkij FW[j,i] = fkij return FW 
       
FW = build_Floyd_Warshall(Atlas,Atlas_vindex,weights) timeit("FW = build_Floyd_Warshall(Atlas,Atlas_vindex,weights)") print 'The Floyd-Warshall Matrix' print FW print FW.str() 
       
5 loops, best of 3: 81 ms per loop
The Floyd-Warshall Matrix
32 x 32 dense matrix over Integer Ring (type 'print obj.str()' to see
all of the entries)
[  0 168 170 534 352 159 300 584 362 240 452 379 458  91 240 577 554 418
97 407 125 628 203 352 246 386 459 506 204 413 388 476]
[168   0 307 702 520 296 437 752 499 408 589 547 626 228 408 745 722 586
265 575 293 796 340 489 383 523 596 674 372 581 556 613]
[170 307   0 586 407 147 288 639 350 351 440 490 513  79 292 629 665 529
267 459 236 687 191 340 172 312 385 558 374 524 440 402]
[534 702 586   0 289 445 716 369 359 403 366 660 245 507 294 322 717 417
631 152 500 393 619 733 546 525 510 264 738 576 146 615]
[352 520 407 289   0 266 537 232 297 114 387 371 106 328 115 405 428 128
397 282 227 325 440 460 367 463 448 261 556 287 143 553]
[159 296 147 445 266   0 272 498 203 332 293 471 372  68 151 488 646 394
256 318 217 546 175 329 128 268 341 417 363 505 299 358]
[300 437 288 716 537 272   0 769 475 481 501 620 643 209 422 741 795 659
397 589 366 817  97 470 202 342 415 688 504 654 570 432]
[584 752 639 369 232 498 769   0 529 346 619 603 126 560 347 485 660 303
629 514 459  93 672 692 599 695 680 341 788 519 223 785]
[362 499 350 359 297 203 475 529   0 397  90 642 403 271 182 330 711 425
459 207 388 573 378 532 306 166 151 404 566 570 326 256]
[240 408 351 403 114 332 481 346 397   0 487 257 220 272 215 519 314 178
285 382 115 388 384 348 427 563 548 375 444 173 257 653]
[452 589 440 366 387 293 501 619  90 487   0 732 493 361 272 240 801 515
549 214 478 663 404 622 299 163 149 411 656 660 416 253]
[379 547 490 660 371 471 620 603 642 257 732   0 477 411 460 776 571 435
424 627 254 645 523 487 566 706 779 632 583 430 514 796]
[458 626 513 245 106 372 643 126 403 220 493 477   0 434 221 361 534 234
503 388 333 219 546 566 473 569 554 217 662 393  99 659]
[ 91 228  79 507 328  68 209 560 271 272 361 411 434   0 213 550 586 450
188 380 157 608 112 261 155 295 368 479 295 445 361 385]
[240 408 292 294 115 151 422 347 182 215 272 460 221 213   0 337 529 243
337 167 206 395 325 439 252 348 333 266 444 388 148 438]
[577 745 629 322 405 488 741 485 330 519 240 776 361 550 337   0 833 533
674 170 543 509 644 776 539 403 389 367 781 692 262 493]
[554 722 665 717 428 646 795 660 711 314 801 571 534 586 529 833   0 492
599 696 429 702 698 662 741 877 862 689 758 487 571 967]
[418 586 529 417 128 394 659 303 425 178 515 435 234 450 243 533 492   0
463 410 293 210 562 526 495 591 576 389 622 351 271 681]
[ 97 265 267 631 397 256 397 629 459 285 549 424 503 188 337 674 599 463
0 504 170 673 300 403 343 483 556 603 301 458 485 573]
[407 575 459 152 282 318 589 514 207 382 214 627 388 380 167 170 696 410
504   0 373 545 492 606 419 373 358 197 611 555 298 463]
[125 293 236 500 227 217 366 459 388 115 478 254 333 157 206 543 429 293
170 373   0 503 269 233 312 452 525 472 329 288 354 542]
[628 796 687 393 325 546 817  93 573 388 663 645 219 608 395 509 702 210
673 545 503   0 720 736 647 739 724 365 832 561 247 829]
[203 340 191 619 440 175  97 672 378 384 404 523 546 112 325 644 698 562
300 492 269 720   0 373 105 245 318 591 407 557 473 335]
[352 489 340 733 460 329 470 692 532 348 622 487 566 261 439 776 662 526
403 606 233 736 373   0 416 556 629 705 556 521 587 646]
[246 383 172 546 367 128 202 599 306 427 299 566 473 155 252 539 741 495
343 419 312 647 105 416   0 140 213 518 450 600 400 230]
[386 523 312 525 463 268 342 695 166 563 163 706 569 295 348 403 877 591
483 373 452 739 245 556 140   0  73 570 590 736 492  90]
[459 596 385 510 448 341 415 680 151 548 149 779 554 368 333 389 862 576
556 358 525 724 318 629 213  73   0 555 663 721 477 163]
[506 674 558 264 261 417 688 341 404 375 411 632 217 479 266 367 689 389
603 197 472 365 591 705 518 570 555   0 710 548 118 660]
[204 372 374 738 556 363 504 788 566 444 656 583 662 295 444 781 758 622
301 611 329 832 407 556 450 590 663 710   0 617 592 680]
[413 581 524 576 287 505 654 519 570 173 660 430 393 445 388 692 487 351
458 555 288 561 557 521 600 736 721 548 617   0 430 826]
[388 556 440 146 143 299 570 223 326 257 416 514  99 361 148 262 571 271
485 298 354 247 473 587 400 492 477 118 592 430   0 582]
[476 613 402 615 553 358 432 785 256 653 253 796 659 385 438 493 967 681
573 463 542 829 335 646 230  90 163 660 680 826 582   0]
5 loops, best of 3: 81 ms per loop
The Floyd-Warshall Matrix
32 x 32 dense matrix over Integer Ring (type 'print obj.str()' to see all of the entries)
[  0 168 170 534 352 159 300 584 362 240 452 379 458  91 240 577 554 418  97 407 125 628 203 352 246 386 459 506 204 413 388 476]
[168   0 307 702 520 296 437 752 499 408 589 547 626 228 408 745 722 586 265 575 293 796 340 489 383 523 596 674 372 581 556 613]
[170 307   0 586 407 147 288 639 350 351 440 490 513  79 292 629 665 529 267 459 236 687 191 340 172 312 385 558 374 524 440 402]
[534 702 586   0 289 445 716 369 359 403 366 660 245 507 294 322 717 417 631 152 500 393 619 733 546 525 510 264 738 576 146 615]
[352 520 407 289   0 266 537 232 297 114 387 371 106 328 115 405 428 128 397 282 227 325 440 460 367 463 448 261 556 287 143 553]
[159 296 147 445 266   0 272 498 203 332 293 471 372  68 151 488 646 394 256 318 217 546 175 329 128 268 341 417 363 505 299 358]
[300 437 288 716 537 272   0 769 475 481 501 620 643 209 422 741 795 659 397 589 366 817  97 470 202 342 415 688 504 654 570 432]
[584 752 639 369 232 498 769   0 529 346 619 603 126 560 347 485 660 303 629 514 459  93 672 692 599 695 680 341 788 519 223 785]
[362 499 350 359 297 203 475 529   0 397  90 642 403 271 182 330 711 425 459 207 388 573 378 532 306 166 151 404 566 570 326 256]
[240 408 351 403 114 332 481 346 397   0 487 257 220 272 215 519 314 178 285 382 115 388 384 348 427 563 548 375 444 173 257 653]
[452 589 440 366 387 293 501 619  90 487   0 732 493 361 272 240 801 515 549 214 478 663 404 622 299 163 149 411 656 660 416 253]
[379 547 490 660 371 471 620 603 642 257 732   0 477 411 460 776 571 435 424 627 254 645 523 487 566 706 779 632 583 430 514 796]
[458 626 513 245 106 372 643 126 403 220 493 477   0 434 221 361 534 234 503 388 333 219 546 566 473 569 554 217 662 393  99 659]
[ 91 228  79 507 328  68 209 560 271 272 361 411 434   0 213 550 586 450 188 380 157 608 112 261 155 295 368 479 295 445 361 385]
[240 408 292 294 115 151 422 347 182 215 272 460 221 213   0 337 529 243 337 167 206 395 325 439 252 348 333 266 444 388 148 438]
[577 745 629 322 405 488 741 485 330 519 240 776 361 550 337   0 833 533 674 170 543 509 644 776 539 403 389 367 781 692 262 493]
[554 722 665 717 428 646 795 660 711 314 801 571 534 586 529 833   0 492 599 696 429 702 698 662 741 877 862 689 758 487 571 967]
[418 586 529 417 128 394 659 303 425 178 515 435 234 450 243 533 492   0 463 410 293 210 562 526 495 591 576 389 622 351 271 681]
[ 97 265 267 631 397 256 397 629 459 285 549 424 503 188 337 674 599 463   0 504 170 673 300 403 343 483 556 603 301 458 485 573]
[407 575 459 152 282 318 589 514 207 382 214 627 388 380 167 170 696 410 504   0 373 545 492 606 419 373 358 197 611 555 298 463]
[125 293 236 500 227 217 366 459 388 115 478 254 333 157 206 543 429 293 170 373   0 503 269 233 312 452 525 472 329 288 354 542]
[628 796 687 393 325 546 817  93 573 388 663 645 219 608 395 509 702 210 673 545 503   0 720 736 647 739 724 365 832 561 247 829]
[203 340 191 619 440 175  97 672 378 384 404 523 546 112 325 644 698 562 300 492 269 720   0 373 105 245 318 591 407 557 473 335]
[352 489 340 733 460 329 470 692 532 348 622 487 566 261 439 776 662 526 403 606 233 736 373   0 416 556 629 705 556 521 587 646]
[246 383 172 546 367 128 202 599 306 427 299 566 473 155 252 539 741 495 343 419 312 647 105 416   0 140 213 518 450 600 400 230]
[386 523 312 525 463 268 342 695 166 563 163 706 569 295 348 403 877 591 483 373 452 739 245 556 140   0  73 570 590 736 492  90]
[459 596 385 510 448 341 415 680 151 548 149 779 554 368 333 389 862 576 556 358 525 724 318 629 213  73   0 555 663 721 477 163]
[506 674 558 264 261 417 688 341 404 375 411 632 217 479 266 367 689 389 603 197 472 365 591 705 518 570 555   0 710 548 118 660]
[204 372 374 738 556 363 504 788 566 444 656 583 662 295 444 781 758 622 301 611 329 832 407 556 450 590 663 710   0 617 592 680]
[413 581 524 576 287 505 654 519 570 173 660 430 393 445 388 692 487 351 458 555 288 561 557 521 600 736 721 548 617   0 430 826]
[388 556 440 146 143 299 570 223 326 257 416 514  99 361 148 262 571 271 485 298 354 247 473 587 400 492 477 118 592 430   0 582]
[476 613 402 615 553 358 432 785 256 653 253 796 659 385 438 493 967 681 573 463 542 829 335 646 230  90 163 660 680 826 582   0]

Once the Floyd Warshall matrix has been constructed it is an easy matter to look up the shortest distance between any two cities.

Exercise 6:  Complete the following routine, short_path_FW, that uses the Floyd-Warshall matrix to determine a path that has that shortest distance between a given pair of cities.

# Determine the shortest path from the start_city to the destination # given the global vertex_list and FW matrix. def short_path_FW(start_city, destination): path = [] sk = Atlas_vindex[start_city] dk = Atlas_vindex[destination] min_distance = FW[sk,dk] current_dist = 0 uk = sk city = start_city while uk != dk: path.append(city) neighbors = Atlas.Adj[city] startDist = 1000000 for next_city in neighbors: tmp = Atlas_vindex[next_city] toTmp = FW[uk, tmp] tmpToDest = FW[tmp, dk] if(tmp == dk): startDist = toTmp vk = tmp city = next_city elif((toTmp+tmpToDest) < startDist): vk = tmp startDist = toTmp + tmpToDest city = next_city current_dist += FW[uk,vk] uk = vk path.append(city) return (min_distance,path) 
       
# An extremely simple test case short_path_FW('Atlanta, GA', 'Augusta, GA') 
       
(151, ['Atlanta, GA', 'Augusta, GA'])
(151, ['Atlanta, GA', 'Augusta, GA'])

The following block uses the preceeding Floyd Warshall matrix and the related shortest path algorithm, to find the shortest route from Wilmington, NC to Memphis, TN.  

It then prints the distance, the path and the timing results.

print short_path_FW('Wilmington, NC', 'Memphis, TN') timeit("short_path_FW('Wilmington, NC', 'Memphis, TN')") 
       
(832, ['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville,
TN', 'Nashville, TN', 'Memphis, TN'])
625 loops, best of 3: 25.3 µs per loop
(832, ['Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN'])
625 loops, best of 3: 25.3 µs per loop

Exercise 7.  Using the preceeding Floyd Warshall matrix and the related shortest path algorithm, short_path_FW, find the shortest route from Daytona_Beach, FL to Lexington, KY.

Then print the distance, the path, and the timing results.

print short_path_FW('Daytona_Beach, FL', 'Lexington, KY') timeit("short_path_FW('Daytona_Beach, FL', 'Lexington, KY')") 
       
(826, ['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta,
GA', 'Knoxville, TN', 'Lexington, KY'])
625 loops, best of 3: 27.5 µs per loop
(826, ['Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY'])
625 loops, best of 3: 27.5 µs per loop

Exercise 8. Using the preceeding Floyd Warshall matrix and the related shortest path algorithm, short_path_FW, find the shortest route from Charleston, SC to Charleston, WV.

Then print the distance, the path, and the timing results.

print short_path_FW('Charleston, SC', 'Charleston, WV') timeit("short_path_FW('Charleston, SC', 'Charleston, WV')") 
       
(698, ['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville,
TN', 'Charleston, WV'])
625 loops, best of 3: 25.7 µs per loop
(698, ['Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV'])
625 loops, best of 3: 25.7 µs per loop