--- a/SmallWorldGraph.py	Sat Jan 05 13:00:07 2013 -0600
+++ b/SmallWorldGraph.py	Sat Jan 05 13:30:58 2013 -0600
@@ -1,6 +1,7 @@
 """This module contains the SmallWorldGraph class for 4.4, exercise 4.
 
 """
+import heapq
 import itertools
 import random
 
@@ -127,6 +128,30 @@
                     queue.append(w)
                     sort_flag = True
 
+    def shortest_path_tree2(self, source):
+        """Finds the length of the shortest path from the source vertex to all
+        other vertices in the graph. This length is stored on the vertices as an
+        attribute named 'dist'. The algorithm used is Dijkstra's with a Heap
+        used to sort/store pending nodes to be examined.
+
+        """
+        for v in self.vertices():
+            v.dist = INFINITY
+        source.dist = 0
+
+        queue = []
+        heapq.heappush(queue, (0, source))
+        while len(queue):
+
+            _, v = heapq.heappop(queue)
+
+            # for each neighbor of v, see if we found a new shortest path
+            for w, e in self[v].iteritems():
+                d = v.dist + e.length
+                if d < w.dist:
+                    w.dist = d
+                    heapq.heappush(queue, (d, w))
+
     def all_pairs_floyd_warshall(self):
         """Finds the shortest paths between all pairs of vertices using the
         Floyd-Warshall algorithm.
@@ -158,7 +183,7 @@
     def big_l(self):
         """Computes the "big-L" value for the graph as per Watts & Strogatz.
 
-        big_l() is defined as the number of edges in the shortest path between
+        L is defined as the number of edges in the shortest path between
         two vertices, averaged over all vertices.
 
         Uses the shortest_path_tree() method, called once for every node.
@@ -177,7 +202,7 @@
     def big_l2(self):
         """Computes the "big-L" value for the graph as per Watts & Strogatz.
 
-        big_l() is defined as the number of edges in the shortest path between
+        L is defined as the number of edges in the shortest path between
         two vertices, averaged over all vertices.
 
         Uses the all_pairs_floyd_warshall() method.
@@ -190,3 +215,23 @@
         if len(result):
             return sum(result) / float(len(result))
         return 0.0
+
+    def big_l3(self):
+        """Computes the "big-L" value for the graph as per Watts & Strogatz.
+
+        L is defined as the number of edges in the shortest path between
+        two vertices, averaged over all vertices.
+
+        Uses the shortest_path_tree2() method, called once for every node.
+
+        """
+        d = {}
+        for v in self.vertices():
+            self.shortest_path_tree2(v)
+            t = [((v, w), w.dist) for w in self.vertices() if v is not w]
+            d.update(t)
+
+        if len(d):
+            return sum(d.values()) / float(len(d))
+        return 0.0
+

--- a/ch4ex4.py	Sat Jan 05 13:00:07 2013 -0600
+++ b/ch4ex4.py	Sat Jan 05 13:30:58 2013 -0600
@@ -11,7 +11,7 @@
 from SmallWorldGraph import SmallWorldGraph
 
 # Use Dijkstra or Floyd-Warshall to compute L
-DIJKSTRA = False
+DIJKSTRA = True
 
 # compute C(0)
 n = 1000
@@ -19,7 +19,7 @@
 vs = [Vertex(str(i)) for i in range(n)]
 g = SmallWorldGraph(vs, k, 0.0)
 c0 = g.clustering_coefficient()
-l0 = g.big_l() if DIJKSTRA else g.big_l2()
+l0 = g.big_l3() if DIJKSTRA else g.big_l2()
 print 'c0 =', c0, 'l0 =', l0
 
 # compute data
@@ -34,7 +34,7 @@
 for p in p_vals:
     g = SmallWorldGraph(vs, k, p)
     c_vals.append(g.clustering_coefficient() / c0)
-    l = g.big_l() if DIJKSTRA else g.big_l2()
+    l = g.big_l3() if DIJKSTRA else g.big_l2()
     l_vals.append(l / l0)
 
 p_vals.insert(0, 0.0)