We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Documentation and code in `floyd_warshall_numpy` are inconsistent
### Current Behavior
<!--- Tell us what happens instead of the expected behavior -->

Using `floyd_warshall_numpy` with a specified set of nodes will only find paths that are confined to that subset of nodes.  I'm not sure I agree with that choice, and certainly the documentation does not make it clear.

### Expected Behavior
<!--- Tell us what should happen -->

Based on the documentation, I would expect it to find a path that starts at one node and ends at another, even if that path must go through additional nodes not in the provided list.

### Steps to Reproduce
<!--- Provide a minimal example that reproduces the bug -->

https://stackoverflow.com/q/65771537/2966723

### Environment
<!--- Please provide details about your local environment -->
Python version:  3.9
NetworkX version:  2.5


### Additional context
<!--- Add any other context about the problem here, screenshots, etc. -->


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `networkx/algorithms/shortest_paths/dense.py`
Content:
```
1 """Floyd-Warshall algorithm for shortest paths.
2 """
3 import networkx as nx
4 
5 __all__ = [
6     "floyd_warshall",
7     "floyd_warshall_predecessor_and_distance",
8     "reconstruct_path",
9     "floyd_warshall_numpy",
10 ]
11 
12 
13 def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
14     """Find all-pairs shortest path lengths using Floyd's algorithm.
15 
16     Parameters
17     ----------
18     G : NetworkX graph
19 
20     nodelist : list, optional
21        The rows and columns are ordered by the nodes in nodelist.
22        If nodelist is None then the ordering is produced by G.nodes().
23 
24     weight: string, optional (default= 'weight')
25        Edge data key corresponding to the edge weight.
26 
27     Returns
28     -------
29     distance : NumPy matrix
30         A matrix of shortest path distances between nodes.
31         If there is no path between to nodes the corresponding matrix entry
32         will be Inf.
33 
34     Notes
35     -----
36     Floyd's algorithm is appropriate for finding shortest paths in
37     dense graphs or graphs with negative weights when Dijkstra's
38     algorithm fails. This algorithm can still fail if there are negative
39     cycles.  It has running time $O(n^3)$ with running space of $O(n^2)$.
40     """
41     import numpy as np
42 
43     # To handle cases when an edge has weight=0, we must make sure that
44     # nonedges are not given the value 0 as well.
45     A = nx.to_numpy_array(
46         G, nodelist=nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
47     )
48     n, m = A.shape
49     np.fill_diagonal(A, 0)  # diagonal elements should be zero
50     for i in range(n):
51         # The second term has the same shape as A due to broadcasting
52         A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
53     return A
54 
55 
56 def floyd_warshall_predecessor_and_distance(G, weight="weight"):
57     """Find all-pairs shortest path lengths using Floyd's algorithm.
58 
59     Parameters
60     ----------
61     G : NetworkX graph
62 
63     weight: string, optional (default= 'weight')
64        Edge data key corresponding to the edge weight.
65 
66     Returns
67     -------
68     predecessor,distance : dictionaries
69        Dictionaries, keyed by source and target, of predecessors and distances
70        in the shortest path.
71 
72     Examples
73     --------
74     >>> G = nx.DiGraph()
75     >>> G.add_weighted_edges_from(
76     ...     [
77     ...         ("s", "u", 10),
78     ...         ("s", "x", 5),
79     ...         ("u", "v", 1),
80     ...         ("u", "x", 2),
81     ...         ("v", "y", 1),
82     ...         ("x", "u", 3),
83     ...         ("x", "v", 5),
84     ...         ("x", "y", 2),
85     ...         ("y", "s", 7),
86     ...         ("y", "v", 6),
87     ...     ]
88     ... )
89     >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
90     >>> print(nx.reconstruct_path("s", "v", predecessors))
91     ['s', 'x', 'u', 'v']
92 
93     Notes
94     -----
95     Floyd's algorithm is appropriate for finding shortest paths
96     in dense graphs or graphs with negative weights when Dijkstra's algorithm
97     fails.  This algorithm can still fail if there are negative cycles.
98     It has running time $O(n^3)$ with running space of $O(n^2)$.
99 
100     See Also
101     --------
102     floyd_warshall
103     floyd_warshall_numpy
104     all_pairs_shortest_path
105     all_pairs_shortest_path_length
106     """
107     from collections import defaultdict
108 
109     # dictionary-of-dictionaries representation for dist and pred
110     # use some defaultdict magick here
111     # for dist the default is the floating point inf value
112     dist = defaultdict(lambda: defaultdict(lambda: float("inf")))
113     for u in G:
114         dist[u][u] = 0
115     pred = defaultdict(dict)
116     # initialize path distance dictionary to be the adjacency matrix
117     # also set the distance to self to 0 (zero diagonal)
118     undirected = not G.is_directed()
119     for u, v, d in G.edges(data=True):
120         e_weight = d.get(weight, 1.0)
121         dist[u][v] = min(e_weight, dist[u][v])
122         pred[u][v] = u
123         if undirected:
124             dist[v][u] = min(e_weight, dist[v][u])
125             pred[v][u] = v
126     for w in G:
127         dist_w = dist[w]  # save recomputation
128         for u in G:
129             dist_u = dist[u]  # save recomputation
130             for v in G:
131                 d = dist_u[w] + dist_w[v]
132                 if dist_u[v] > d:
133                     dist_u[v] = d
134                     pred[u][v] = pred[w][v]
135     return dict(pred), dict(dist)
136 
137 
138 def reconstruct_path(source, target, predecessors):
139     """Reconstruct a path from source to target using the predecessors
140     dict as returned by floyd_warshall_predecessor_and_distance
141 
142     Parameters
143     ----------
144     source : node
145        Starting node for path
146 
147     target : node
148        Ending node for path
149 
150     predecessors: dictionary
151        Dictionary, keyed by source and target, of predecessors in the
152        shortest path, as returned by floyd_warshall_predecessor_and_distance
153 
154     Returns
155     -------
156     path : list
157        A list of nodes containing the shortest path from source to target
158 
159        If source and target are the same, an empty list is returned
160 
161     Notes
162     -----
163     This function is meant to give more applicability to the
164     floyd_warshall_predecessor_and_distance function
165 
166     See Also
167     --------
168     floyd_warshall_predecessor_and_distance
169     """
170     if source == target:
171         return []
172     prev = predecessors[source]
173     curr = prev[target]
174     path = [target, curr]
175     while curr != source:
176         curr = prev[curr]
177         path.append(curr)
178     return list(reversed(path))
179 
180 
181 def floyd_warshall(G, weight="weight"):
182     """Find all-pairs shortest path lengths using Floyd's algorithm.
183 
184     Parameters
185     ----------
186     G : NetworkX graph
187 
188     weight: string, optional (default= 'weight')
189        Edge data key corresponding to the edge weight.
190 
191 
192     Returns
193     -------
194     distance : dict
195        A dictionary,  keyed by source and target, of shortest paths distances
196        between nodes.
197 
198     Notes
199     -----
200     Floyd's algorithm is appropriate for finding shortest paths
201     in dense graphs or graphs with negative weights when Dijkstra's algorithm
202     fails.  This algorithm can still fail if there are negative cycles.
203     It has running time $O(n^3)$ with running space of $O(n^2)$.
204 
205     See Also
206     --------
207     floyd_warshall_predecessor_and_distance
208     floyd_warshall_numpy
209     all_pairs_shortest_path
210     all_pairs_shortest_path_length
211     """
212     # could make this its own function to reduce memory costs
213     return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]
214
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/networkx/algorithms/shortest_paths/dense.py b/networkx/algorithms/shortest_paths/dense.py
--- a/networkx/algorithms/shortest_paths/dense.py
+++ b/networkx/algorithms/shortest_paths/dense.py
@@ -13,37 +13,57 @@
 def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
     """Find all-pairs shortest path lengths using Floyd's algorithm.
 
+    This algorithm for finding shortest paths takes advantage of
+    matrix representations of a graph and works well for dense
+    graphs where all-pairs shortest path lengths are desired.
+    The results are returned as a NumPy array, distance[i, j],
+    where i and j are the indexes of two nodes in nodelist.
+    The entry distance[i, j] is the distance along a shortest
+    path from i to j. If no path exists the distance is Inf.
+
     Parameters
     ----------
     G : NetworkX graph
 
-    nodelist : list, optional
+    nodelist : list, optional (default=G.nodes)
        The rows and columns are ordered by the nodes in nodelist.
-       If nodelist is None then the ordering is produced by G.nodes().
+       If nodelist is None then the ordering is produced by G.nodes.
+       Nodelist should include all nodes in G.
 
-    weight: string, optional (default= 'weight')
+    weight: string, optional (default='weight')
        Edge data key corresponding to the edge weight.
 
     Returns
     -------
     distance : NumPy matrix
         A matrix of shortest path distances between nodes.
-        If there is no path between to nodes the corresponding matrix entry
-        will be Inf.
+        If there is no path between two nodes the value is Inf.
 
     Notes
     -----
     Floyd's algorithm is appropriate for finding shortest paths in
     dense graphs or graphs with negative weights when Dijkstra's
     algorithm fails. This algorithm can still fail if there are negative
-    cycles.  It has running time $O(n^3)$ with running space of $O(n^2)$.
+    cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.
+
+    Raises
+    ------
+    NetworkXError
+        If nodelist is not a list of the nodes in G.
     """
     import numpy as np
 
+    if nodelist is not None:
+        if not (len(nodelist) == len(G) == len(set(nodelist))):
+            raise nx.NetworkXError(
+                "nodelist must contain every node in G with no repeats."
+                "If you wanted a subgraph of G use G.subgraph(nodelist)"
+            )
+
     # To handle cases when an edge has weight=0, we must make sure that
     # nonedges are not given the value 0 as well.
     A = nx.to_numpy_array(
-        G, nodelist=nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
+        G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
     )
     n, m = A.shape
     np.fill_diagonal(A, 0)  # diagonal elements should be zero

{"golden_diff": "diff --git a/networkx/algorithms/shortest_paths/dense.py b/networkx/algorithms/shortest_paths/dense.py\n--- a/networkx/algorithms/shortest_paths/dense.py\n+++ b/networkx/algorithms/shortest_paths/dense.py\n@@ -13,37 +13,57 @@\n def floyd_warshall_numpy(G, nodelist=None, weight=\"weight\"):\n     \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n \n+    This algorithm for finding shortest paths takes advantage of\n+    matrix representations of a graph and works well for dense\n+    graphs where all-pairs shortest path lengths are desired.\n+    The results are returned as a NumPy array, distance[i, j],\n+    where i and j are the indexes of two nodes in nodelist.\n+    The entry distance[i, j] is the distance along a shortest\n+    path from i to j. If no path exists the distance is Inf.\n+\n     Parameters\n     ----------\n     G : NetworkX graph\n \n-    nodelist : list, optional\n+    nodelist : list, optional (default=G.nodes)\n        The rows and columns are ordered by the nodes in nodelist.\n-       If nodelist is None then the ordering is produced by G.nodes().\n+       If nodelist is None then the ordering is produced by G.nodes.\n+       Nodelist should include all nodes in G.\n \n-    weight: string, optional (default= 'weight')\n+    weight: string, optional (default='weight')\n        Edge data key corresponding to the edge weight.\n \n     Returns\n     -------\n     distance : NumPy matrix\n         A matrix of shortest path distances between nodes.\n-        If there is no path between to nodes the corresponding matrix entry\n-        will be Inf.\n+        If there is no path between two nodes the value is Inf.\n \n     Notes\n     -----\n     Floyd's algorithm is appropriate for finding shortest paths in\n     dense graphs or graphs with negative weights when Dijkstra's\n     algorithm fails. This algorithm can still fail if there are negative\n-    cycles.  It has running time $O(n^3)$ with running space of $O(n^2)$.\n+    cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.\n+\n+    Raises\n+    ------\n+    NetworkXError\n+        If nodelist is not a list of the nodes in G.\n     \"\"\"\n     import numpy as np\n \n+    if nodelist is not None:\n+        if not (len(nodelist) == len(G) == len(set(nodelist))):\n+            raise nx.NetworkXError(\n+                \"nodelist must contain every node in G with no repeats.\"\n+                \"If you wanted a subgraph of G use G.subgraph(nodelist)\"\n+            )\n+\n     # To handle cases when an edge has weight=0, we must make sure that\n     # nonedges are not given the value 0 as well.\n     A = nx.to_numpy_array(\n-        G, nodelist=nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf\n+        G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf\n     )\n     n, m = A.shape\n     np.fill_diagonal(A, 0)  # diagonal elements should be zero\n", "issue": "Documentation and code in `floyd_warshall_numpy` are inconsistent\n### Current Behavior\r\n<!--- Tell us what happens instead of the expected behavior -->\r\n\r\nUsing `floyd_warshall_numpy` with a specified set of nodes will only find paths that are confined to that subset of nodes.  I'm not sure I agree with that choice, and certainly the documentation does not make it clear.\r\n\r\n### Expected Behavior\r\n<!--- Tell us what should happen -->\r\n\r\nBased on the documentation, I would expect it to find a path that starts at one node and ends at another, even if that path must go through additional nodes not in the provided list.\r\n\r\n### Steps to Reproduce\r\n<!--- Provide a minimal example that reproduces the bug -->\r\n\r\nhttps://stackoverflow.com/q/65771537/2966723\r\n\r\n### Environment\r\n<!--- Please provide details about your local environment -->\r\nPython version:  3.9\r\nNetworkX version:  2.5\r\n\r\n\r\n### Additional context\r\n<!--- Add any other context about the problem here, screenshots, etc. -->\r\n\n", "before_files": [{"content": "\"\"\"Floyd-Warshall algorithm for shortest paths.\n\"\"\"\nimport networkx as nx\n\n__all__ = [\n    \"floyd_warshall\",\n    \"floyd_warshall_predecessor_and_distance\",\n    \"reconstruct_path\",\n    \"floyd_warshall_numpy\",\n]\n\n\ndef floyd_warshall_numpy(G, nodelist=None, weight=\"weight\"):\n    \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    nodelist : list, optional\n       The rows and columns are ordered by the nodes in nodelist.\n       If nodelist is None then the ordering is produced by G.nodes().\n\n    weight: string, optional (default= 'weight')\n       Edge data key corresponding to the edge weight.\n\n    Returns\n    -------\n    distance : NumPy matrix\n        A matrix of shortest path distances between nodes.\n        If there is no path between to nodes the corresponding matrix entry\n        will be Inf.\n\n    Notes\n    -----\n    Floyd's algorithm is appropriate for finding shortest paths in\n    dense graphs or graphs with negative weights when Dijkstra's\n    algorithm fails. This algorithm can still fail if there are negative\n    cycles.  It has running time $O(n^3)$ with running space of $O(n^2)$.\n    \"\"\"\n    import numpy as np\n\n    # To handle cases when an edge has weight=0, we must make sure that\n    # nonedges are not given the value 0 as well.\n    A = nx.to_numpy_array(\n        G, nodelist=nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf\n    )\n    n, m = A.shape\n    np.fill_diagonal(A, 0)  # diagonal elements should be zero\n    for i in range(n):\n        # The second term has the same shape as A due to broadcasting\n        A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])\n    return A\n\n\ndef floyd_warshall_predecessor_and_distance(G, weight=\"weight\"):\n    \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    weight: string, optional (default= 'weight')\n       Edge data key corresponding to the edge weight.\n\n    Returns\n    -------\n    predecessor,distance : dictionaries\n       Dictionaries, keyed by source and target, of predecessors and distances\n       in the shortest path.\n\n    Examples\n    --------\n    >>> G = nx.DiGraph()\n    >>> G.add_weighted_edges_from(\n    ...     [\n    ...         (\"s\", \"u\", 10),\n    ...         (\"s\", \"x\", 5),\n    ...         (\"u\", \"v\", 1),\n    ...         (\"u\", \"x\", 2),\n    ...         (\"v\", \"y\", 1),\n    ...         (\"x\", \"u\", 3),\n    ...         (\"x\", \"v\", 5),\n    ...         (\"x\", \"y\", 2),\n    ...         (\"y\", \"s\", 7),\n    ...         (\"y\", \"v\", 6),\n    ...     ]\n    ... )\n    >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)\n    >>> print(nx.reconstruct_path(\"s\", \"v\", predecessors))\n    ['s', 'x', 'u', 'v']\n\n    Notes\n    -----\n    Floyd's algorithm is appropriate for finding shortest paths\n    in dense graphs or graphs with negative weights when Dijkstra's algorithm\n    fails.  This algorithm can still fail if there are negative cycles.\n    It has running time $O(n^3)$ with running space of $O(n^2)$.\n\n    See Also\n    --------\n    floyd_warshall\n    floyd_warshall_numpy\n    all_pairs_shortest_path\n    all_pairs_shortest_path_length\n    \"\"\"\n    from collections import defaultdict\n\n    # dictionary-of-dictionaries representation for dist and pred\n    # use some defaultdict magick here\n    # for dist the default is the floating point inf value\n    dist = defaultdict(lambda: defaultdict(lambda: float(\"inf\")))\n    for u in G:\n        dist[u][u] = 0\n    pred = defaultdict(dict)\n    # initialize path distance dictionary to be the adjacency matrix\n    # also set the distance to self to 0 (zero diagonal)\n    undirected = not G.is_directed()\n    for u, v, d in G.edges(data=True):\n        e_weight = d.get(weight, 1.0)\n        dist[u][v] = min(e_weight, dist[u][v])\n        pred[u][v] = u\n        if undirected:\n            dist[v][u] = min(e_weight, dist[v][u])\n            pred[v][u] = v\n    for w in G:\n        dist_w = dist[w]  # save recomputation\n        for u in G:\n            dist_u = dist[u]  # save recomputation\n            for v in G:\n                d = dist_u[w] + dist_w[v]\n                if dist_u[v] > d:\n                    dist_u[v] = d\n                    pred[u][v] = pred[w][v]\n    return dict(pred), dict(dist)\n\n\ndef reconstruct_path(source, target, predecessors):\n    \"\"\"Reconstruct a path from source to target using the predecessors\n    dict as returned by floyd_warshall_predecessor_and_distance\n\n    Parameters\n    ----------\n    source : node\n       Starting node for path\n\n    target : node\n       Ending node for path\n\n    predecessors: dictionary\n       Dictionary, keyed by source and target, of predecessors in the\n       shortest path, as returned by floyd_warshall_predecessor_and_distance\n\n    Returns\n    -------\n    path : list\n       A list of nodes containing the shortest path from source to target\n\n       If source and target are the same, an empty list is returned\n\n    Notes\n    -----\n    This function is meant to give more applicability to the\n    floyd_warshall_predecessor_and_distance function\n\n    See Also\n    --------\n    floyd_warshall_predecessor_and_distance\n    \"\"\"\n    if source == target:\n        return []\n    prev = predecessors[source]\n    curr = prev[target]\n    path = [target, curr]\n    while curr != source:\n        curr = prev[curr]\n        path.append(curr)\n    return list(reversed(path))\n\n\ndef floyd_warshall(G, weight=\"weight\"):\n    \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    weight: string, optional (default= 'weight')\n       Edge data key corresponding to the edge weight.\n\n\n    Returns\n    -------\n    distance : dict\n       A dictionary,  keyed by source and target, of shortest paths distances\n       between nodes.\n\n    Notes\n    -----\n    Floyd's algorithm is appropriate for finding shortest paths\n    in dense graphs or graphs with negative weights when Dijkstra's algorithm\n    fails.  This algorithm can still fail if there are negative cycles.\n    It has running time $O(n^3)$ with running space of $O(n^2)$.\n\n    See Also\n    --------\n    floyd_warshall_predecessor_and_distance\n    floyd_warshall_numpy\n    all_pairs_shortest_path\n    all_pairs_shortest_path_length\n    \"\"\"\n    # could make this its own function to reduce memory costs\n    return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]\n", "path": "networkx/algorithms/shortest_paths/dense.py"}], "after_files": [{"content": "\"\"\"Floyd-Warshall algorithm for shortest paths.\n\"\"\"\nimport networkx as nx\n\n__all__ = [\n    \"floyd_warshall\",\n    \"floyd_warshall_predecessor_and_distance\",\n    \"reconstruct_path\",\n    \"floyd_warshall_numpy\",\n]\n\n\ndef floyd_warshall_numpy(G, nodelist=None, weight=\"weight\"):\n    \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n\n    This algorithm for finding shortest paths takes advantage of\n    matrix representations of a graph and works well for dense\n    graphs where all-pairs shortest path lengths are desired.\n    The results are returned as a NumPy array, distance[i, j],\n    where i and j are the indexes of two nodes in nodelist.\n    The entry distance[i, j] is the distance along a shortest\n    path from i to j. If no path exists the distance is Inf.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    nodelist : list, optional (default=G.nodes)\n       The rows and columns are ordered by the nodes in nodelist.\n       If nodelist is None then the ordering is produced by G.nodes.\n       Nodelist should include all nodes in G.\n\n    weight: string, optional (default='weight')\n       Edge data key corresponding to the edge weight.\n\n    Returns\n    -------\n    distance : NumPy matrix\n        A matrix of shortest path distances between nodes.\n        If there is no path between two nodes the value is Inf.\n\n    Notes\n    -----\n    Floyd's algorithm is appropriate for finding shortest paths in\n    dense graphs or graphs with negative weights when Dijkstra's\n    algorithm fails. This algorithm can still fail if there are negative\n    cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.\n\n    Raises\n    ------\n    NetworkXError\n        If nodelist is not a list of the nodes in G.\n    \"\"\"\n    import numpy as np\n\n    if nodelist is not None:\n        if not (len(nodelist) == len(G) == len(set(nodelist))):\n            raise nx.NetworkXError(\n                \"nodelist must contain every node in G with no repeats.\"\n                \"If you wanted a subgraph of G use G.subgraph(nodelist)\"\n            )\n\n    # To handle cases when an edge has weight=0, we must make sure that\n    # nonedges are not given the value 0 as well.\n    A = nx.to_numpy_array(\n        G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf\n    )\n    n, m = A.shape\n    np.fill_diagonal(A, 0)  # diagonal elements should be zero\n    for i in range(n):\n        # The second term has the same shape as A due to broadcasting\n        A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])\n    return A\n\n\ndef floyd_warshall_predecessor_and_distance(G, weight=\"weight\"):\n    \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    weight: string, optional (default= 'weight')\n       Edge data key corresponding to the edge weight.\n\n    Returns\n    -------\n    predecessor,distance : dictionaries\n       Dictionaries, keyed by source and target, of predecessors and distances\n       in the shortest path.\n\n    Examples\n    --------\n    >>> G = nx.DiGraph()\n    >>> G.add_weighted_edges_from(\n    ...     [\n    ...         (\"s\", \"u\", 10),\n    ...         (\"s\", \"x\", 5),\n    ...         (\"u\", \"v\", 1),\n    ...         (\"u\", \"x\", 2),\n    ...         (\"v\", \"y\", 1),\n    ...         (\"x\", \"u\", 3),\n    ...         (\"x\", \"v\", 5),\n    ...         (\"x\", \"y\", 2),\n    ...         (\"y\", \"s\", 7),\n    ...         (\"y\", \"v\", 6),\n    ...     ]\n    ... )\n    >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)\n    >>> print(nx.reconstruct_path(\"s\", \"v\", predecessors))\n    ['s', 'x', 'u', 'v']\n\n    Notes\n    -----\n    Floyd's algorithm is appropriate for finding shortest paths\n    in dense graphs or graphs with negative weights when Dijkstra's algorithm\n    fails.  This algorithm can still fail if there are negative cycles.\n    It has running time $O(n^3)$ with running space of $O(n^2)$.\n\n    See Also\n    --------\n    floyd_warshall\n    floyd_warshall_numpy\n    all_pairs_shortest_path\n    all_pairs_shortest_path_length\n    \"\"\"\n    from collections import defaultdict\n\n    # dictionary-of-dictionaries representation for dist and pred\n    # use some defaultdict magick here\n    # for dist the default is the floating point inf value\n    dist = defaultdict(lambda: defaultdict(lambda: float(\"inf\")))\n    for u in G:\n        dist[u][u] = 0\n    pred = defaultdict(dict)\n    # initialize path distance dictionary to be the adjacency matrix\n    # also set the distance to self to 0 (zero diagonal)\n    undirected = not G.is_directed()\n    for u, v, d in G.edges(data=True):\n        e_weight = d.get(weight, 1.0)\n        dist[u][v] = min(e_weight, dist[u][v])\n        pred[u][v] = u\n        if undirected:\n            dist[v][u] = min(e_weight, dist[v][u])\n            pred[v][u] = v\n    for w in G:\n        dist_w = dist[w]  # save recomputation\n        for u in G:\n            dist_u = dist[u]  # save recomputation\n            for v in G:\n                d = dist_u[w] + dist_w[v]\n                if dist_u[v] > d:\n                    dist_u[v] = d\n                    pred[u][v] = pred[w][v]\n    return dict(pred), dict(dist)\n\n\ndef reconstruct_path(source, target, predecessors):\n    \"\"\"Reconstruct a path from source to target using the predecessors\n    dict as returned by floyd_warshall_predecessor_and_distance\n\n    Parameters\n    ----------\n    source : node\n       Starting node for path\n\n    target : node\n       Ending node for path\n\n    predecessors: dictionary\n       Dictionary, keyed by source and target, of predecessors in the\n       shortest path, as returned by floyd_warshall_predecessor_and_distance\n\n    Returns\n    -------\n    path : list\n       A list of nodes containing the shortest path from source to target\n\n       If source and target are the same, an empty list is returned\n\n    Notes\n    -----\n    This function is meant to give more applicability to the\n    floyd_warshall_predecessor_and_distance function\n\n    See Also\n    --------\n    floyd_warshall_predecessor_and_distance\n    \"\"\"\n    if source == target:\n        return []\n    prev = predecessors[source]\n    curr = prev[target]\n    path = [target, curr]\n    while curr != source:\n        curr = prev[curr]\n        path.append(curr)\n    return list(reversed(path))\n\n\ndef floyd_warshall(G, weight=\"weight\"):\n    \"\"\"Find all-pairs shortest path lengths using Floyd's algorithm.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n\n    weight: string, optional (default= 'weight')\n       Edge data key corresponding to the edge weight.\n\n\n    Returns\n    -------\n    distance : dict\n       A dictionary,  keyed by source and target, of shortest paths distances\n       between nodes.\n\n    Notes\n    -----\n    Floyd's algorithm is appropriate for finding shortest paths\n    in dense graphs or graphs with negative weights when Dijkstra's algorithm\n    fails.  This algorithm can still fail if there are negative cycles.\n    It has running time $O(n^3)$ with running space of $O(n^2)$.\n\n    See Also\n    --------\n    floyd_warshall_predecessor_and_distance\n    floyd_warshall_numpy\n    all_pairs_shortest_path\n    all_pairs_shortest_path_length\n    \"\"\"\n    # could make this its own function to reduce memory costs\n    return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]\n", "path": "networkx/algorithms/shortest_paths/dense.py"}]}