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.
|
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.
|
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
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.
|
Create a Graph, G2, then add weights to make it a Network. Finally display the Network.
(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']} (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']} |
|
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.
|
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 |
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 |
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.
|
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 |
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 |
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.
|
|
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 ) |
|
(Initializing a graph with 32 vertices and 67 edges) (Initializing a graph with 32 vertices and 67 edges) |
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".
The following function computes the straight-line distance between two cities. The block also verifies that the calculation and the specified distances are 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.
|
The following code uses the three algorithms to find the shortest route from Wilmington, NC to 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.
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.
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 |
|
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.
|
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.
Best-First ('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN') 832 [84, 2, 332] Best-First ('Wilmington, NC', 'Charlotte, NC', 'Asheville, NC', 'Knoxville, TN', 'Nashville, TN', 'Memphis, TN') 832 [84, 2, 332] |
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.
Best-First ('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY') 826 [280, 6, 1377] Best-First ('Daytona_Beach, FL', 'Jacksonville, FL', 'Tifton, GA', 'Atlanta, GA', 'Knoxville, TN', 'Lexington, KY') 826 [280, 6, 1377] |
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.
Best-First ('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV') 698 [323, 5, 1212] Best-First ('Charleston, SC', 'Columbia, SC', 'Asheville, NC', 'Knoxville, TN', 'Charleston, WV') 698 [323, 5, 1212] |
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))
\]
{'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.
|
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.
|
(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.
(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.
(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.
(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 |