Source code online books for professionals by professionals

Dijkstra’s algorithm. Find the shortest paths from one node to all others in a weighted graph, as long as there are no 
negative edge weights. Traverses the graph, repeatedly selecting the next node using a priority queue (a heap). The 
priority is the current distance estimate of the node. These estimates are updated whenever a shortcut is found from  
a visited node. The running time is Q((m+n) lg n), which is simply Q(m lg n) if the graph is connected.
Double-ended queues. FIFO queues implemented using linked lists (or linked lists of arrays), so that inserting 
and extracting objects at either end can be done in constant time. An efficient implementation can be found in the 
collections.deque class. (See the “Black Box” sidebar on the topic in Chapter 5.)
Dynamic arrays, vectors. The idea of having extra capacity in an array, so appending is efficient. By relocating 
the contents to a bigger array, growing it by a constant factor, when it fills up, appends can be constant in average 
(amortized) time. (See Chapter 2.)
Edmonds–Karp. The concrete instantiation of the Floyd–Warshall method where traversal is performed using BFS. 
Finds min-cost flow in Q(nm
2
) time. (See Listing 10-4.)
Floyd–Warshall. Finds shortest paths from each node to all others. In iteration k, only the first k nodes (in some 
ordering) are allowed as intermediate nodes along the paths. Extending from k–1 involves checking whether the 
shortest paths to and from k via the first k–1 nodes is shorter than simply going directly via these nodes. (That is, node 
k is either used or not, for every shortest path.) Running time is Q(n
3
). (See Listing 9-6.)
Ford–Fulkerson. A general approach to solving max-flow problems. The method involves repeatedly traversing  
the graph to find a so-called augmenting path, a path along which the flow can be increased (augmented). The  
flow can be increased along an edge if it has extra capacity, or it can be increased backward across an edge  
(that is, canceled) if there is flow along the edge. Thus, the traversal can move both forward and backward along  
the directed edges, depending on the flow across them. The running time depends on the traversal strategy used. 
(See Listing 10-4.)
Gale–Shapley. Finds a stable set of marriages given preference rankings for a set of men and women. Any unengaged 
men propose to the most preferred woman they haven’t proposed to. Each woman will choose her favorite among her 
current suitors (possibly staying with her fiancé). Can be implemented with quadratic running time. (See the sidebar 
“Eager Suitors and Stable Marriages” in Chapter 7.)
2
Note that finding matchings in general (possibly nonbipartite) graphs is not covered in this book.

---

Appendix B 
■
 List of proBLems And ALgorithms
264
Gnome sort. A simple sorting algorithm with quadratic running time. Probably not an algorithm you’ll use in 
practice. (See Listing 3-1.)