Repository: networkx/networkx

Issue:
`networkx.version` shadows any other module named `version` if imported first
Steps to reproduce:

```
$ pip freeze | grep networkx
networkx==1.11
$ touch version.py
$ python -c 'import version; print(version)'
<module 'version' from '/Users/ben/scratch/version.py'>
$ python -c 'import networkx; import version; print(version)'
<module 'version' from '/Users/ben/.virtualenvs/personal/lib/python3.6/site-packages/networkx/version.py'>
```

Reading the code, it looks like the `release` module is adding the networkx package to `sys.path`, importing version and deleting it again?

Discussion:

Patch:
diff --git a/doc/release/migration_guide_from_1.x_to_2.0.rst b/doc/release/migration_guide_from_1.x_to_2.0.rst
index d403fcb15..087605643 100644
--- a/doc/release/migration_guide_from_1.x_to_2.0.rst
+++ b/doc/release/migration_guide_from_1.x_to_2.0.rst
@@ -10,12 +10,37 @@ We have made some major changes to the methods in the Multi/Di/Graph classes.
 The methods changed are explained with examples below.
 
 With the release of NetworkX 2.0 we are moving to a view/iterator reporting API.
+We have moved many methods from reporting lists or dicts to iterating over
+the information. Most of the changes in this regard are in the base classes.
 Methods that used to return containers now return views (inspired from
 [dictionary views](https://docs.python.org/3/library/stdtypes.html#dict-views)
 in Python) and methods that returned iterators have been removed.
-For example, ``G.nodes`` (or ``G.nodes()``)  now returns a NodeView and
-``G.nodes_iter()`` has been removed. The Graph attributes G.node and G.edge
-have also been removed in favor of using G.nodes[n] and G.edges[u, v].
+The methods which create new graphs have changed in the depth of data copying.
+G.subgraph/edge_subgraph/reverse/to_directed/to_undirected are affected.
+Many now have options for view creation instead of copying data. The depth
+of the dta copying may have also changed.
+
+One View example is ``G.nodes`` (or ``G.nodes()``) which now returns a
+dict-like NodeView while ``G.nodes_iter()`` has been removed. Similarly
+for views with ``G.edges`` and removing ``G.edges_iter``.
+The Graph attributes G.node and G.edge have been removed in favor of using
+G.nodes[n] and G.edges[u, v].
+Finally, the selfloop methods and add_path/star/cycle have been moved from
+graph methods to networkx functions.
+
+We expect that these changes will break some code. We have tried to make
+them break the code in ways that raise exceptions, so it will be obvious
+that code is broken.
+
+There are also a number of improvements to the codebase outside of the base
+graph classes. These are too numerous to catalog here, but a couple obvious
+ones include:
+- centering of nodes in drawing/nx_pylab,
+- iterator vs dict output from a few shortest_path routines
+
+-------
+
+Some demonstrations:
 
     >>> import networkx as nx
     >>> G = nx.complete_graph(5)
@@ -40,7 +65,7 @@ If you want a list of nodes you can use the Python list function
 G.nodes is set-like allowing set operations. It is also dict-like in that you
 can look up node data with G.nodes[n]['weight']. You can still use the calling
 interface G.nodes(data='weight') to iterate over node/data pairs. In addition
-to the dict-like views keys/values/items, G.nodes has a data-view 
+to the dict-like views keys/values/items, G.nodes has a data-view
 G.nodes.data('weight').  The new EdgeView G.edges has similar features for edges.
 
 By adding views NetworkX supports some new features like set operations on
@@ -89,7 +114,7 @@ If ``n`` is a node in ``G``, then ``G.neighbors(n)`` returns an iterator.
     >>> list(G.neighbors(2))
     [0, 1, 3, 4]
 
-DiGraphs behave similar to Graphs, but have a few more methods.
+DiGraphViews behave similar to GraphViews, but have a few more methods.
 
     >>> D = nx.DiGraph()
     >>> D.add_edges_from([(1, 2), (2, 3), (1, 3), (2, 4)])
@@ -127,7 +152,7 @@ DiGraphs behave similar to Graphs, but have a few more methods.
     [1]
 
 The same changes apply to MultiGraphs and MultiDiGraphs.
- 
+
 -------
 
 The order of arguments to ``set_edge_attributes`` and ``set_node_attributes`` has
@@ -150,10 +175,10 @@ can be refactored as
     >>> G = nx.Graph([(1, 2), (1, 3)])
     >>> nx.set_node_attributes(G, name='label', values={1: 'one', 2: 'two', 3: 'three'})
     >>> nx.set_edge_attributes(G, name='label', values={(1, 2): 'path1', (2, 3): 'path2'})
- 
+
 -------
 
-Some methods have been removed from the base graph class and placed into the main 
+Some methods have been removed from the base graph class and placed into the main
 networkx namespace. These are:  G.add_path, G.add_star, G.add_cycle, G.number_of_selfloops,
 G.nodes_with_selfloops, and G.selfloop_edges.   These are replaced by nx.path_graph(G, ...)
 nx.add_star(G, ...), nx.selfloop_edges(G), etc.
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst
index 627cf38d6..a35d9beaf 100644
--- a/doc/release/release_dev.rst
+++ b/doc/release/release_dev.rst
@@ -189,6 +189,9 @@ API Changes
    G.node and G.edge are removed. Their functionality are replaced by G.nodes
    and G.edges.
 
+* [`#2620 <https://github.com/networkx/networkx/pull/2620>`_]
+   Removed ``draw_nx``, please use ``draw`` or ``draw_networkx``.
+
 Deprecations
 ------------
 
diff --git a/networkx/algorithms/centrality/harmonic.py b/networkx/algorithms/centrality/harmonic.py
index c851acaae..571dca4ab 100644
--- a/networkx/algorithms/centrality/harmonic.py
+++ b/networkx/algorithms/centrality/harmonic.py
@@ -65,4 +65,5 @@ def harmonic_centrality(G, nbunch=None, distance=None):
     if G.is_directed():
         G = G.reverse()
     spl = partial(nx.shortest_path_length, G, weight=distance)
-    return {u: sum(1 / d if d > 0 else 0 for v, d in spl(source=u)) for u in G.nbunch_iter(nbunch)}
+    return {u: sum(1 / d if d > 0 else 0 for v, d in spl(source=u).items())
+            for u in G.nbunch_iter(nbunch)}
diff --git a/networkx/algorithms/connectivity/stoerwagner.py b/networkx/algorithms/connectivity/stoerwagner.py
index 40b543497..3f55934c2 100644
--- a/networkx/algorithms/connectivity/stoerwagner.py
+++ b/networkx/algorithms/connectivity/stoerwagner.py
@@ -151,7 +151,7 @@ def stoer_wagner(G, weight='weight', heap=BinaryHeap):
     G = nx.Graph(islice(contractions, best_phase))
     v = contractions[best_phase][1]
     G.add_node(v)
-    reachable = set(n for n, d in nx.single_source_shortest_path_length(G, v))
+    reachable = set(nx.single_source_shortest_path_length(G, v))
     partition = (list(reachable), list(nodes - reachable))
 
     return cut_value, partition
diff --git a/networkx/algorithms/dag.py b/networkx/algorithms/dag.py
index 473e4ce90..437fb9ed9 100644
--- a/networkx/algorithms/dag.py
+++ b/networkx/algorithms/dag.py
@@ -51,7 +51,8 @@ def descendants(G, source):
     """
     if not G.has_node(source):
         raise nx.NetworkXError("The node %s is not in the graph." % source)
-    des = set(n for n, d in nx.shortest_path_length(G, source=source)) - set([source])
+    spl = nx.shortest_path_length(G, source=source)
+    des = set(spl) - set([source])
     return des
 
 
@@ -71,7 +72,8 @@ def ancestors(G, source):
     """
     if not G.has_node(source):
         raise nx.NetworkXError("The node %s is not in the graph." % source)
-    anc = set(n for n, d in nx.shortest_path_length(G, target=source)) - set([source])
+    spl = nx.shortest_path_length(G, target=source)
+    anc = set(spl) - set([source])
     return anc
 
 
diff --git a/networkx/algorithms/distance_measures.py b/networkx/algorithms/distance_measures.py
index de0f10d2c..c2d9ec9d3 100644
--- a/networkx/algorithms/distance_measures.py
+++ b/networkx/algorithms/distance_measures.py
@@ -223,7 +223,7 @@ def eccentricity(G, v=None, sp=None):
     e = {}
     for n in G.nbunch_iter(v):
         if sp is None:
-            length = dict(networkx.single_source_shortest_path_length(G, n))
+            length = networkx.single_source_shortest_path_length(G, n)
             L = len(length)
         else:
             try:
diff --git a/networkx/algorithms/efficiency.py b/networkx/algorithms/efficiency.py
index 63cf0f2a9..46b2fdcd3 100644
--- a/networkx/algorithms/efficiency.py
+++ b/networkx/algorithms/efficiency.py
@@ -12,6 +12,7 @@ from __future__ import division
 from itertools import permutations
 
 import networkx as nx
+from networkx.exception import NetworkXNoPath
 from ..utils import not_implemented_for
 
 __all__ = ['efficiency', 'local_efficiency', 'global_efficiency']
@@ -22,7 +23,8 @@ def efficiency(G, u, v):
     """Returns the efficiency of a pair of nodes in a graph.
 
     The *efficiency* of a pair of nodes is the multiplicative inverse of the
-    shortest path distance between the nodes [1]_.
+    shortest path distance between the nodes [1]_. Returns 0 if no path
+    between nodes.
 
     Parameters
     ----------
@@ -53,7 +55,11 @@ def efficiency(G, u, v):
            <http://dx.doi.org/10.1103/PhysRevLett.87.198701>
 
     """
-    return 1 / nx.shortest_path_length(G, u, v)
+    try:
+        eff = 1 / nx.shortest_path_length(G, u, v)
+    except NetworkXNoPath:
+        eff = 0
+    return eff
 
 
 @not_implemented_for('directed')
@@ -93,11 +99,15 @@ def global_efficiency(G):
     """
     n = len(G)
     denom = n * (n - 1)
+    if denom != 0:
+        g_eff = sum(efficiency(G, u, v) for u, v in permutations(G, 2)) / denom
+    else:
+        g_eff = 0
     # TODO This can be made more efficient by computing all pairs shortest
     # path lengths in parallel.
     #
     # TODO This summation can be trivially parallelized.
-    return sum(efficiency(G, u, v) for u, v in permutations(G, 2)) / denom
+    return g_eff
 
 
 @not_implemented_for('directed')
diff --git a/networkx/drawing/nx_pylab.py b/networkx/drawing/nx_pylab.py
index 4a5e5ee4b..79c012c36 100644
--- a/networkx/drawing/nx_pylab.py
+++ b/networkx/drawing/nx_pylab.py
@@ -982,11 +982,6 @@ def draw_shell(G, **kwargs):
     draw(G, shell_layout(G, nlist=nlist), **kwargs)
 
 
-def draw_nx(G, pos, **kwds):
-    """For backward compatibility; use draw or draw_networkx."""
-    draw(G, pos, **kwds)
-
-
 def apply_alpha(colors, alpha, elem_list, cmap=None, vmin=None, vmax=None):
     """Apply an alpha (or list of alphas) to the colors provided.
 
diff --git a/networkx/release.py b/networkx/release.py
index a76968da9..54af63702 100644
--- a/networkx/release.py
+++ b/networkx/release.py
@@ -101,9 +101,9 @@ vcs_info = %(vcs_info)r
             # This is *good*, and the most likely place users will be when
             # running setup.py. We do not want to overwrite version.py.
             # Grab the version so that setup can use it.
-            sys.path.insert(0, basedir)
+            #sys.path.insert(0, basedir)
             from version import version
-            del sys.path[0]
+            #del sys.path[0]
         else:
             # This is *bad*.  It means the user might have a tarball that
             # does not include version.py.  Let this error raise so we can
@@ -152,7 +152,7 @@ def get_info(dynamic=True):
         # This is where most final releases of NetworkX will be.
         # All info should come from version.py. If it does not exist, then
         # no vcs information will be provided.
-        sys.path.insert(0, basedir)
+        #sys.path.insert(0, basedir)
         try:
             from version import date, date_info, version, version_info, vcs_info
         except ImportError:
@@ -160,7 +160,7 @@ def get_info(dynamic=True):
             vcs_info = (None, (None, None))
         else:
             revision = vcs_info[1][0]
-        del sys.path[0]
+        #del sys.path[0]
 
     if import_failed or (dynamic and not dynamic_failed):
         # We are here if:


Test patch:
diff --git a/networkx/algorithms/shortest_paths/generic.py b/networkx/algorithms/shortest_paths/generic.py
index b5144e04b..fe8e68526 100644
--- a/networkx/algorithms/shortest_paths/generic.py
+++ b/networkx/algorithms/shortest_paths/generic.py
@@ -113,9 +113,9 @@ def shortest_path(G, source=None, target=None, weight=None):
         if target is None:
             # Find paths between all pairs.
             if weight is None:
-                paths = nx.all_pairs_shortest_path(G)
+                paths = dict(nx.all_pairs_shortest_path(G))
             else:
-                paths = nx.all_pairs_dijkstra_path(G, weight=weight)
+                paths = dict(nx.all_pairs_dijkstra_path(G, weight=weight))
         else:
             # Find paths from all nodes co-accessible to the target.
             with nx.utils.reversed(G):
@@ -174,19 +174,15 @@ def shortest_path_length(G, source=None, target=None, weight=None):
         If the source and target are both specified, return the length of
         the shortest path from the source to the target.
 
-        If only the source is specified, return a tuple
-        (target, shortest path length) iterator, where shortest path lengths
-        are the lengths of the shortest path from the source to one of the
-        targets.
+        If only the source is specified, return a dict keyed by target
+        to the shortest path length from the source to that target.
 
-        If only the target is specified, return a tuple
-        (source, shortest path length) iterator, where shortest path lengths
-        are the lengths of the shortest path from one of the sources
-        to the target.
+        If only the target is specified, return a dict keyed by source
+        to the shortest path length from that source to the target.
 
-        If neither the source nor target are specified, return a
-        (source, dictionary) iterator with dictionary keyed by target and
-        shortest path length as the key value.
+        If neither the source nor target are specified, return an iterator
+        over (source, dictionary) where dictionary is keyed by target to
+        shortest path length from source to that target.
 
     Raises
     ------
@@ -199,13 +195,13 @@ def shortest_path_length(G, source=None, target=None, weight=None):
     >>> nx.shortest_path_length(G, source=0, target=4)
     4
     >>> p = nx.shortest_path_length(G, source=0) # target not specified
-    >>> dict(p)[4]
+    >>> p[4]
     4
     >>> p = nx.shortest_path_length(G, target=4) # source not specified
-    >>> dict(p)[0]
+    >>> p[0]
     4
-    >>> p = nx.shortest_path_length(G) # source,target not specified
-    >>> dict(p)[0][4]
+    >>> p = dict(nx.shortest_path_length(G)) # source,target not specified
+    >>> p[0][4]
     4
 
     Notes
@@ -239,7 +235,7 @@ def shortest_path_length(G, source=None, target=None, weight=None):
                     # We need to exhaust the iterator as Graph needs
                     # to be reversed.
                     path_length = nx.single_source_shortest_path_length
-                    paths = list(path_length(G, target))
+                    paths = path_length(G, target)
                 else:
                     path_length = nx.single_source_dijkstra_path_length
                     paths = path_length(G, target, weight=weight)
@@ -333,7 +329,7 @@ def average_shortest_path_length(G, weight=None):
         ssdpl = nx.single_source_dijkstra_path_length
         path_length = lambda v: ssdpl(G, v, weight=weight)
     # Sum the distances for each (ordered) pair of source and target node.
-    s = sum(l for u in G for v, l in path_length(u))
+    s = sum(l for u in G for l in path_length(u).values())
     return s / (n * (n - 1))
 
 
diff --git a/networkx/algorithms/shortest_paths/tests/test_generic.py b/networkx/algorithms/shortest_paths/tests/test_generic.py
index 021bfb774..1d992412a 100644
--- a/networkx/algorithms/shortest_paths/tests/test_generic.py
+++ b/networkx/algorithms/shortest_paths/tests/test_generic.py
@@ -96,14 +96,14 @@ class TestGenericPath:
 
     def test_all_pairs_shortest_path(self):
         p=nx.shortest_path(self.cycle)
-        assert_equal(p[0][3],[0,1,2,3])
-        assert_equal(p,nx.all_pairs_shortest_path(self.cycle))
+        assert_equal(p[0][3], [0, 1, 2, 3])
+        assert_equal(p, dict(nx.all_pairs_shortest_path(self.cycle)))
         p=nx.shortest_path(self.grid)
         validate_grid_path(4, 4, 1, 12, p[1][12])
         # now with weights
         p=nx.shortest_path(self.cycle,weight='weight')
-        assert_equal(p[0][3],[0,1,2,3])
-        assert_equal(p,nx.all_pairs_dijkstra_path(self.cycle))
+        assert_equal(p[0][3],[0, 1, 2, 3])
+        assert_equal(p, dict(nx.all_pairs_dijkstra_path(self.cycle)))
         p=nx.shortest_path(self.grid,weight='weight')
         validate_grid_path(4, 4, 1, 12, p[1][12])
 
diff --git a/networkx/algorithms/shortest_paths/tests/test_unweighted.py b/networkx/algorithms/shortest_paths/tests/test_unweighted.py
index 570bfe482..0b876c21f 100644
--- a/networkx/algorithms/shortest_paths/tests/test_unweighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_unweighted.py
@@ -75,9 +75,9 @@ class TestUnweightedPath:
         assert_equal(dict(pl(self.directed_cycle, 0)), lengths)
 
     def test_all_pairs_shortest_path(self):
-        p=nx.all_pairs_shortest_path(self.cycle)
+        p=dict(nx.all_pairs_shortest_path(self.cycle))
         assert_equal(p[0][3],[0,1,2,3])
-        p=nx.all_pairs_shortest_path(self.grid)
+        p=dict(nx.all_pairs_shortest_path(self.grid))
         validate_grid_path(4, 4, 1, 12, p[1][12])
 
     def test_all_pairs_shortest_path_length(self):
diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py
index 2641521d6..0ba63cc56 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -239,6 +239,35 @@ class TestWeightedPath(WeightedTestBase):
         assert_equal(distance, 1 / 10)
         assert_equal(path, [0, 2])
 
+    def test_all_pairs_dijkstra_path(self):
+        cycle=nx.cycle_graph(7)
+        p=dict(nx.all_pairs_dijkstra_path(cycle))
+        assert_equal(p[0][3], [0, 1, 2, 3])
+
+        cycle[1][2]['weight'] = 10
+        p=dict(nx.all_pairs_dijkstra_path(cycle))
+        assert_equal(p[0][3], [0, 6, 5, 4, 3])
+
+    def test_all_pairs_dijkstra_path_length(self):
+        cycle=nx.cycle_graph(7)
+        pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
+        assert_equal(pl[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
+
+        cycle[1][2]['weight'] = 10
+        pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
+        assert_equal(pl[0], {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1})
+
+    def test_all_pairs_dijkstra(self):
+        cycle=nx.cycle_graph(7)
+        out = dict(nx.all_pairs_dijkstra(cycle))
+        assert_equal(out[0][0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
+        assert_equal(out[0][1][3], [0, 1, 2, 3])
+
+        cycle[1][2]['weight'] = 10
+        out = dict(nx.all_pairs_dijkstra(cycle))
+        assert_equal(out[0][0], {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1})
+        assert_equal(out[0][1][3], [0, 6, 5, 4, 3])
+
 
 class TestDijkstraPathLength(object):
     """Unit tests for the :func:`networkx.dijkstra_path_length`
@@ -298,6 +327,13 @@ class TestMultiSourceDijkstra(object):
         assert_equal(distances, expected_distances)
         assert_equal(paths, expected_paths)
 
+    def test_simple_paths(self):
+        G = nx.path_graph(4)
+        lengths = nx.multi_source_dijkstra_path_length(G, [0])
+        assert_equal(lengths, {n: n for n in G})
+        paths = nx.multi_source_dijkstra_path(G, [0])
+        assert_equal(paths, {n: list(range(n+1)) for n in G})
+
 
 class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
 
@@ -305,7 +341,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         G = nx.DiGraph()
         G.add_node(0)
         assert_equal(nx.single_source_bellman_ford_path(G, 0), {0: [0]})
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(G, 0)), {0: 0})
+        assert_equal(nx.single_source_bellman_ford_path_length(G, 0), {0: 0})
         assert_equal(nx.single_source_bellman_ford(G, 0), ({0: 0}, {0: [0]}))
         assert_equal(nx.bellman_ford_predecessor_and_distance(G, 0), ({0: [None]}, {0: 0}))
         assert_equal(nx.goldberg_radzik(G, 0), ({0: None}, {0: 0}))
@@ -340,7 +376,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         G.add_edge(1, 2, weight=-3)
         assert_equal(nx.single_source_bellman_ford_path(G, 0),
                      {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]})
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(G, 0)),
+        assert_equal(nx.single_source_bellman_ford_path_length(G, 0),
                      {0: 0, 1: 1, 2: -2, 3: -1, 4: 0})
         assert_equal(nx.single_source_bellman_ford(G, 0),
                      ({0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
@@ -358,7 +394,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         G.add_edge(10, 12)
         assert_equal(nx.single_source_bellman_ford_path(G, 0),
                      {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5]})
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(G, 0)),
+        assert_equal(nx.single_source_bellman_ford_path_length(G, 0),
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})
         assert_equal(nx.single_source_bellman_ford(G, 0),
                      ({0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
@@ -378,7 +414,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
                           ('C', 'A', {'load': 2})])
         assert_equal(nx.single_source_bellman_ford_path(G, 0, weight='load'),
                      {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5]})
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(G, 0, weight='load')),
+        assert_equal(nx.single_source_bellman_ford_path_length(G, 0, weight='load'),
                      {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1})
         assert_equal(nx.single_source_bellman_ford(G, 0, weight='load'),
                      ({0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
@@ -394,7 +430,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         assert_equal(nx.bellman_ford_path(self.MXG, 's', 'v'), ['s', 'x', 'u', 'v'])
         assert_equal(nx.bellman_ford_path_length(self.MXG, 's', 'v'), 9)
         assert_equal(nx.single_source_bellman_ford_path(self.MXG, 's')['v'], ['s', 'x', 'u', 'v'])
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(self.MXG, 's'))['v'], 9)
+        assert_equal(nx.single_source_bellman_ford_path_length(self.MXG, 's')['v'], 9)
         D, P = nx.single_source_bellman_ford(self.MXG, 's', target='v')
         assert_equal(D, 9)
         assert_equal(P, ['s', 'x', 'u', 'v'])
@@ -407,7 +443,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         assert_equal(nx.bellman_ford_path(self.MXG4, 0, 2), [0, 1, 2])
         assert_equal(nx.bellman_ford_path_length(self.MXG4, 0, 2), 4)
         assert_equal(nx.single_source_bellman_ford_path(self.MXG4, 0)[2], [0, 1, 2])
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(self.MXG4, 0))[2], 4)
+        assert_equal(nx.single_source_bellman_ford_path_length(self.MXG4, 0)[2], 4)
         D, P = nx.single_source_bellman_ford(self.MXG4, 0, target=2)
         assert_equal(D, 4)
         assert_equal(P, [0, 1, 2])
@@ -422,7 +458,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         assert_equal(nx.bellman_ford_path(self.XG, 's', 'v'), ['s', 'x', 'u', 'v'])
         assert_equal(nx.bellman_ford_path_length(self.XG, 's', 'v'), 9)
         assert_equal(nx.single_source_bellman_ford_path(self.XG, 's')['v'], ['s', 'x', 'u', 'v'])
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(self.XG, 's'))['v'], 9)
+        assert_equal(nx.single_source_bellman_ford_path_length(self.XG, 's')['v'], 9)
         D, P = nx.single_source_bellman_ford(self.XG, 's', target='v')
         assert_equal(D, 9)
         assert_equal(P, ['s', 'x', 'u', 'v'])
@@ -437,7 +473,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
         G = nx.path_graph(4)
         assert_equal(nx.single_source_bellman_ford_path(G, 0),
                      {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3]})
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(G, 0)),
+        assert_equal(nx.single_source_bellman_ford_path_length(G, 0),
                      {0: 0, 1: 1, 2: 2, 3: 3})
         assert_equal(nx.single_source_bellman_ford(G, 0),
                      ({0: 0, 1: 1, 2: 2, 3: 3}, {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3]}))
@@ -447,7 +483,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
                      ({0: None, 1: 0, 2: 1, 3: 2}, {0: 0, 1: 1, 2: 2, 3: 3}))
         assert_equal(nx.single_source_bellman_ford_path(G, 3),
                      {0: [3, 2, 1, 0], 1: [3, 2, 1], 2: [3, 2], 3: [3]})
-        assert_equal(dict(nx.single_source_bellman_ford_path_length(G, 3)),
+        assert_equal(nx.single_source_bellman_ford_path_length(G, 3),
                      {0: 3, 1: 2, 2: 1, 3: 0})
         assert_equal(nx.single_source_bellman_ford(G, 3),
                      ({0: 3, 1: 2, 2: 1, 3: 0}, {0: [3, 2, 1, 0], 1: [3, 2, 1], 2: [3, 2], 3: [3]}))
diff --git a/networkx/algorithms/shortest_paths/unweighted.py b/networkx/algorithms/shortest_paths/unweighted.py
index 54410e7ea..0c870c245 100644
--- a/networkx/algorithms/shortest_paths/unweighted.py
+++ b/networkx/algorithms/shortest_paths/unweighted.py
@@ -37,13 +37,13 @@ def single_source_shortest_path_length(G, source, cutoff=None):
 
     Returns
     -------
-    lengths : iterator
-        (target, shortest path length) iterator
+    lengths : dict
+        Dict keyed by node to shortest path length to source.
 
     Examples
     --------
     >>> G = nx.path_graph(5)
-    >>> length = dict(nx.single_source_shortest_path_length(G, 0))
+    >>> length = nx.single_source_shortest_path_length(G, 0)
     >>> length[4]
     4
     >>> for node in length:
@@ -63,7 +63,7 @@ def single_source_shortest_path_length(G, source, cutoff=None):
     if cutoff is None:
         cutoff = float('inf')
     nextlevel = {source: 1}
-    return _single_shortest_path_length(G.adj, nextlevel, cutoff)
+    return dict(_single_shortest_path_length(G.adj, nextlevel, cutoff))
 
 
 def _single_shortest_path_length(adj, firstlevel, cutoff):
@@ -183,7 +183,7 @@ def all_pairs_shortest_path_length(G, cutoff=None):
     length = single_source_shortest_path_length
     # TODO This can be trivially parallelized.
     for n in G:
-        yield (n, dict(length(G, n, cutoff=cutoff)))
+        yield (n, length(G, n, cutoff=cutoff))
 
 
 def bidirectional_shortest_path(G, source, target):
@@ -340,7 +340,7 @@ def single_source_shortest_path(G, source, cutoff=None):
         cutoff = float('inf')
     nextlevel = {source: 1}     # list of nodes to check at next level
     paths = {source: [source]}  # paths dictionary  (paths to key from source)
-    return _single_shortest_path(G.adj, nextlevel, paths, cutoff, join)
+    return dict(_single_shortest_path(G.adj, nextlevel, paths, cutoff, join))
 
 
 def _single_shortest_path(adj, firstlevel, paths, cutoff, join):
@@ -423,7 +423,7 @@ def single_target_shortest_path(G, target, cutoff=None):
         cutoff = float('inf')
     nextlevel = {target: 1}     # list of nodes to check at next level
     paths = {target: [target]}  # paths dictionary  (paths to key from source)
-    return _single_shortest_path(adj, nextlevel, paths, cutoff, join)
+    return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join))
 
 
 def all_pairs_shortest_path(G, cutoff=None):
@@ -445,7 +445,7 @@ def all_pairs_shortest_path(G, cutoff=None):
     Examples
     --------
     >>> G = nx.path_graph(5)
-    >>> path = nx.all_pairs_shortest_path(G)
+    >>> path = dict(nx.all_pairs_shortest_path(G))
     >>> print(path[0][4])
     [0, 1, 2, 3, 4]
 
@@ -455,7 +455,8 @@ def all_pairs_shortest_path(G, cutoff=None):
 
     """
     # TODO This can be trivially parallelized.
-    return {n: single_source_shortest_path(G, n, cutoff=cutoff) for n in G}
+    for n in G:
+        yield (n, single_source_shortest_path(G, n, cutoff=cutoff))
 
 
 def predecessor(G, source, target=None, cutoff=None, return_seen=None):
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index a597bbdb4..caa5e85c7 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -31,6 +31,7 @@ __all__ = ['dijkstra_path',
            'multi_source_dijkstra',
            'multi_source_dijkstra_path',
            'multi_source_dijkstra_path_length',
+           'all_pairs_dijkstra',
            'all_pairs_dijkstra_path',
            'all_pairs_dijkstra_path_length',
            'dijkstra_predecessor_and_distance',
@@ -323,13 +324,13 @@ def single_source_dijkstra_path_length(G, source, cutoff=None,
 
     Returns
     -------
-    length : iterator
-        (target, shortest path length) iterator
+    length : dict
+        Dict keyed by node to shortest path length from source.
 
     Examples
     --------
     >>> G = nx.path_graph(5)
-    >>> length = dict(nx.single_source_dijkstra_path_length(G, 0))
+    >>> length = nx.single_source_dijkstra_path_length(G, 0)
     >>> length[4]
     4
     >>> for node in [0, 1, 2, 3, 4]:
@@ -396,11 +397,12 @@ def single_source_dijkstra(G, source, target=None, cutoff=None,
 
     Returns
     -------
-    distance, path : pair of dictionaries, or numeric and list
-       If target is None, returns a tuple of two dictionaries keyed by node.
-       The first dictionary stores distance from one of the source nodes.
-       The second stores the path from one of the sources to that node.
-       If target is not None, returns a tuple of (distance, path) where
+    distance, path : pair of dictionaries, or numeric and list.
+       If target is None, paths and lengths to all nodes are computed.
+       The return value is a tuple of two dictionaries keyed by target nodes.
+       The first dictionary stores distance to each target node.
+       The second stores the path to each target node.
+       If target is not None, returns a tuple (distance, path), where
        distance is the distance from source to target and path is a list
        representing the path from source to target.
 
@@ -559,13 +561,13 @@ def multi_source_dijkstra_path_length(G, sources, cutoff=None,
 
     Returns
     -------
-    length : iterator
-        (target, shortest path length) iterator
+    length : dict
+        Dict keyed by node to shortest path length to nearest source.
 
     Examples
     --------
     >>> G = nx.path_graph(5)
-    >>> length = dict(nx.multi_source_dijkstra_path_length(G, {0, 4}))
+    >>> length = nx.multi_source_dijkstra_path_length(G, {0, 4})
     >>> for node in [0, 1, 2, 3, 4]:
     ...     print('{}: {}'.format(node, length[node]))
     0: 0
@@ -596,9 +598,7 @@ def multi_source_dijkstra_path_length(G, sources, cutoff=None,
     if not sources:
         raise ValueError('sources must not be empty')
     weight = _weight_function(G, weight)
-    dist = _dijkstra_multisource(G, sources, weight, cutoff=cutoff)
-    # TODO In Python 3.3+, this should be `yield from dist.items()`.
-    return iter(dist.items())
+    return _dijkstra_multisource(G, sources, weight, cutoff=cutoff)
 
 
 def multi_source_dijkstra(G, sources, target=None, cutoff=None,
@@ -889,6 +889,73 @@ def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight='weight'):
     return (pred, _dijkstra(G, source, weight, pred=pred, cutoff=cutoff))
 
 
+def all_pairs_dijkstra(G, cutoff=None, weight='weight'):
+    """Find shortest weighted paths and lengths between all nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    cutoff : integer or float, optional
+       Depth to stop the search. Only return paths with length <= cutoff.
+
+    weight : string or function
+       If this is a string, then edge weights will be accessed via the
+       edge attribute with this key (that is, the weight of the edge
+       joining `u` to `v` will be ``G.edge[u][v][weight]``). If no
+       such edge attribute exists, the weight of the edge is assumed to
+       be one.
+
+       If this is a function, the weight of an edge is the value
+       returned by the function. The function must accept exactly three
+       positional arguments: the two endpoints of an edge and the
+       dictionary of edge attributes for that edge. The function must
+       return a number.
+
+    Yields
+    ------
+    (node, (distance, path)) : (node obj, (dict, dict))
+        Each source node has two associated dicts. The first holds distance
+        keyed by target and the second holds paths keyed by target.
+        (See single_source_dijkstra for the source/target node terminology.)
+        If desired you can apply `dict()` to this function to create a dict
+        keyed by source node to the two dicts.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> len_path = dict(nx.all_pairs_dijkstra(G))
+    >>> print(len_path[3][0][1])
+    2
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print('3 - {}: {}'.format(node, len_path[3][0][node]))
+    3 - 0: 3
+    3 - 1: 2
+    3 - 2: 1
+    3 - 3: 0
+    3 - 4: 1
+    >>> len_path[3][1][1]
+    [3, 2, 1]
+    >>> for n, (dist, path) in nx.all_pairs_dijkstra(G):
+    ...     print(path[1])
+    [0, 1]
+    [1]
+    [2, 1]
+    [3, 2, 1]
+    [4, 3, 2, 1]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The yielded dicts only have keys for reachable nodes.
+    """
+    for n in G:
+        dist, path = single_source_dijkstra(G, n, cutoff=cutoff, weight=weight)
+        yield (n, (dist, path))
+
+
 def all_pairs_dijkstra_path_length(G, cutoff=None, weight='weight'):
     """Compute shortest path lengths between all nodes in a weighted graph.
 
@@ -943,7 +1010,7 @@ def all_pairs_dijkstra_path_length(G, cutoff=None, weight='weight'):
     """
     length = single_source_dijkstra_path_length
     for n in G:
-        yield (n, dict(length(G, n, cutoff=cutoff, weight=weight)))
+        yield (n, length(G, n, cutoff=cutoff, weight=weight))
 
 
 def all_pairs_dijkstra_path(G, cutoff=None, weight='weight'):
@@ -976,8 +1043,8 @@ def all_pairs_dijkstra_path(G, cutoff=None, weight='weight'):
 
     Examples
     --------
-    >>> G=nx.path_graph(5)
-    >>> path=nx.all_pairs_dijkstra_path(G)
+    >>> G = nx.path_graph(5)
+    >>> path = dict(nx.all_pairs_dijkstra_path(G))
     >>> print(path[0][4])
     [0, 1, 2, 3, 4]
 
@@ -993,7 +1060,8 @@ def all_pairs_dijkstra_path(G, cutoff=None, weight='weight'):
     """
     path = single_source_dijkstra_path
     # TODO This can be trivially parallelized.
-    return {n: path(G, n, cutoff=cutoff, weight=weight) for n in G}
+    for n in G:
+        yield (n, path(G, n, cutoff=cutoff, weight=weight))
 
 
 def bellman_ford(G, source, weight='weight'):
@@ -1416,8 +1484,7 @@ def single_source_bellman_ford_path_length(G, source,
 
     """
     weight = _weight_function(G, weight)
-
-    return iter(_bellman_ford(G, [source], weight, cutoff=cutoff).items())
+    return _bellman_ford(G, [source], weight, cutoff=cutoff)
 
 
 def single_source_bellman_ford(G, source,
@@ -1566,8 +1633,8 @@ def all_pairs_bellman_ford_path(G, cutoff=None, weight='weight'):
 
     Examples
     --------
-    >>> G=nx.path_graph(5)
-    >>> path=nx.all_pairs_bellman_ford_path(G)
+    >>> G = nx.path_graph(5)
+    >>> path = dict(nx.all_pairs_bellman_ford_path(G))
     >>> print(path[0][4])
     [0, 1, 2, 3, 4]
 
@@ -1583,7 +1650,8 @@ def all_pairs_bellman_ford_path(G, cutoff=None, weight='weight'):
     """
     path = single_source_bellman_ford_path
     # TODO This can be trivially parallelized.
-    return {n: path(G, n, cutoff=cutoff, weight=weight) for n in G}
+    for n in G:
+        yield (n, path(G, n, cutoff=cutoff, weight=weight))
 
 
 def goldberg_radzik(G, source, weight='weight'):
diff --git a/networkx/algorithms/tests/test_efficiency.py b/networkx/algorithms/tests/test_efficiency.py
index 989f8eed5..ba501d1b2 100644
--- a/networkx/algorithms/tests/test_efficiency.py
+++ b/networkx/algorithms/tests/test_efficiency.py
@@ -1,54 +1,68 @@
 # test_efficiency.py - unit tests for the efficiency module
 #
-# Copyright 2015 NetworkX developers.
+# Copyright 2015-2017 NetworkX developers.
 #
 # This file is part of NetworkX.
 #
 # NetworkX is distributed under a BSD license; see LICENSE.txt for more
 # information.
 """Unit tests for the :mod:`networkx.algorithms.efficiency` module."""
+
 from __future__ import division
 from unittest import TestCase
-
 from nose.tools import assert_equal
-
 import networkx as nx
 
 
-def test_efficiency():
-    G = nx.cycle_graph(4)
-    assert_equal(nx.efficiency(G, 0, 1), 1)
-    assert_equal(nx.efficiency(G, 0, 2), 1 / 2)
-
+class TestEfficiency:
 
-def test_global_efficiency():
-    G = nx.cycle_graph(4)
-    assert_equal(nx.global_efficiency(G), 5 / 6)
+    def __init__(self):
+        # G1 is a disconnected graph
+        self.G1 = nx.Graph()
+        self.G1.add_nodes_from([1, 2, 3])
+        # G2 is a cycle graph
+        self.G2 = nx.cycle_graph(4)
+        # G3 is the triangle graph with one additional edge
+        self.G3 = nx.lollipop_graph(3, 1)
 
+    def test_efficiency_disconnected_nodes(self):
+        """
+        When nodes are disconnected, efficiency is 0
+        """
+        assert_equal(nx.efficiency(self.G1, 1, 2), 0)
 
-def test_complete_graph_global_efficiency():
-    """Tests that the average global efficiency of the complete graph is
-    one.
+    def test_local_efficiency_disconnected_graph(self):
+        """
+        In a disconnected graph the efficiency is 0
+        """
+        assert_equal(nx.local_efficiency(self.G1), 0)
 
-    """
-    for n in range(10):
-        G = nx.complete_graph(5)
-        assert_equal(nx.global_efficiency(G), 1)
+    def test_efficiency(self):
+        assert_equal(nx.efficiency(self.G2, 0, 1), 1)
+        assert_equal(nx.efficiency(self.G2, 0, 2), 1 / 2)
 
+    def test_global_efficiency(self):
+        assert_equal(nx.global_efficiency(self.G2), 5 / 6)
 
-class TestLocalEfficiency(TestCase):
-    """Unit tests for the local efficiency function."""
+    def test_global_efficiency_complete_graph(self):
+        """
+        Tests that the average global efficiency of the complete graph is one.
+        """
+        for n in range(2, 10):
+            G = nx.complete_graph(n)
+            assert_equal(nx.global_efficiency(G), 1)
 
-    def test_complete_graph(self):
-        G = nx.complete_graph(4)
-        assert_equal(nx.local_efficiency(G), 1)
+    def test_local_efficiency_complete_graph(self):
+        """
+        Test that the local efficiency for a complete graph should be one.
+        """
+        for n in range(2, 10):
+            G = nx.complete_graph(n)
+            assert_equal(nx.local_efficiency(G), 1)
 
     def test_using_ego_graph(self):
-        """Test that the ego graph is used when computing local efficiency.
-
+        """
+        Test that the ego graph is used when computing local efficiency.
         For more information, see GitHub issue #2233.
-
         """
-        # This is the triangle graph with one additional edge.
-        G = nx.lollipop_graph(3, 1)
-        assert_equal(nx.local_efficiency(G), 23 / 24)
+        assert_equal(nx.local_efficiency(self.G3), 23 / 24)
diff --git a/networkx/algorithms/tests/test_lowest_common_ancestors.py b/networkx/algorithms/tests/test_lowest_common_ancestors.py
index 5160a4aca..3d984b3bf 100644
--- a/networkx/algorithms/tests/test_lowest_common_ancestors.py
+++ b/networkx/algorithms/tests/test_lowest_common_ancestors.py
@@ -162,7 +162,7 @@ class TestDAGLCA:
         self.DG.add_edge(6, 2)
         self.DG.add_edge(7, 2)
 
-        self.root_distance = dict(nx.shortest_path_length(self.DG, source=0))
+        self.root_distance = nx.shortest_path_length(self.DG, source=0)
 
         self.gold = {(1, 1): 1,
                      (1, 2): 1,
@@ -212,7 +212,7 @@ class TestDAGLCA:
         else:
             roots = [n for n, deg in G.in_degree if deg == 0]
             assert(len(roots) == 1)
-            root_distance = dict(nx.shortest_path_length(G, source=roots[0]))
+            root_distance = nx.shortest_path_length(G, source=roots[0])
 
         for a, b in ((min(pair), max(pair)) for pair in chain(d1, d2)):
             assert_equal(root_distance[get_pair(d1, a, b)],
diff --git a/networkx/algorithms/tests/test_threshold.py b/networkx/algorithms/tests/test_threshold.py
index 8562d8ec2..cc76d7cc0 100644
--- a/networkx/algorithms/tests/test_threshold.py
+++ b/networkx/algorithms/tests/test_threshold.py
@@ -69,7 +69,7 @@ class TestGeneratorThreshold():
         for j,pl in enumerate(spl):
             n=cs1[j][0]
             spld[n]=pl
-        assert_equal(spld, dict(nx.single_source_shortest_path_length(G, 3)))
+        assert_equal(spld, nx.single_source_shortest_path_length(G, 3))
 
     def test_weights_thresholds(self):
         wseq=[3,4,3,3,5,6,5,4,5,6]