Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Floyd-Warshall algorithm for shortest paths."""
3from collections import defaultdict
5import networkx as nx
6from networkx.algorithms.shortest_paths.weighted import _weight_function
8__all__ = [
9 "floyd_warshall",
10 "floyd_warshall_predecessor_and_distance",
11 "reconstruct_path",
12 "floyd_warshall_numpy",
13 "floyd_warshall_tree",
14]
17def _init_pred_dist(G, weight):
18 """Initialize pred and dist to be used in Floyd Warshall algorithms"""
19 # dictionary-of-dictionaries representation for dist and pred
20 # use some defaultdict magick here
21 # for dist the default is the floating point inf value
22 dist = defaultdict(lambda: defaultdict(lambda: float("inf")))
23 pred = defaultdict(dict)
24 # initialize path distance dictionary to be the adjacency matrix
25 # also set the distance to self to 0 (zero diagonal)
26 weight = _weight_function(G, weight)
27 for u, unbr in G._adj.items():
28 for v, e_attr in unbr.items():
29 cost = weight(u, v, e_attr)
30 if cost is not None: # for hidden edge, weight() returns None
31 dist[u][v] = cost
32 pred[u][v] = u
33 dist[u][u] = 0
34 return pred, dist
37@nx._dispatchable(edge_attrs="weight")
38def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
39 """Find all-pairs shortest path lengths using Floyd's algorithm.
41 This algorithm for finding shortest paths takes advantage of
42 matrix representations of a graph and works well for dense
43 graphs where all-pairs shortest path lengths are desired.
44 The results are returned as a NumPy array, distance[i, j],
45 where i and j are the indexes of two nodes in nodelist.
46 The entry distance[i, j] is the distance along a shortest
47 path from i to j. If no path exists the distance is Inf.
49 Parameters
50 ----------
51 G : NetworkX graph
53 nodelist : list, optional (default=G.nodes)
54 The rows and columns are ordered by the nodes in nodelist.
55 If nodelist is None then the ordering is produced by G.nodes.
56 Nodelist should include all nodes in G.
58 weight: string, optional (default='weight')
59 Edge data key corresponding to the edge weight.
61 Returns
62 -------
63 distance : 2D numpy.ndarray
64 A numpy array of shortest path distances between nodes.
65 If there is no path between two nodes the value is Inf.
67 Examples
68 --------
69 >>> G = nx.DiGraph()
70 >>> G.add_weighted_edges_from(
71 ... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
72 ... )
73 >>> nx.floyd_warshall_numpy(G)
74 array([[ 0., 5., 7., 4.],
75 [inf, 0., 2., -1.],
76 [inf, inf, 0., -3.],
77 [inf, inf, 8., 0.]])
79 Notes
80 -----
81 Floyd's algorithm is appropriate for finding shortest paths in
82 dense graphs or graphs with negative weights when Dijkstra's
83 algorithm fails. This algorithm can still fail if there are negative
84 cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.
86 Raises
87 ------
88 NetworkXError
89 If nodelist is not a list of the nodes in G.
90 """
91 import numpy as np
93 if nodelist is not None:
94 if not (len(nodelist) == len(G) == len(set(nodelist))):
95 raise nx.NetworkXError(
96 "nodelist must contain every node in G with no repeats."
97 "If you wanted a subgraph of G use G.subgraph(nodelist)"
98 )
100 # To handle cases when an edge has weight=0, we must make sure that
101 # nonedges are not given the value 0 as well.
102 A = nx.to_numpy_array(
103 G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
104 )
105 n, m = A.shape
106 np.fill_diagonal(A, 0) # diagonal elements should be zero
107 for i in range(n):
108 # The second term has the same shape as A due to broadcasting
109 A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
110 return A
113@nx._dispatchable(edge_attrs="weight")
114def floyd_warshall_tree(G, weight="weight"):
115 r"""Find all-pairs shortest path lengths using a Tree-based
116 modification of Floyd's algorithm.
118 This variant implements the Tree algorithm of Brodnik, Grgurovic and Pozar.
119 It differs from the classical Floyd Warshall algorithm by using a shortest
120 path tree rooted at each intermediate vertex w. For every w, the algorithm
121 builds a tree ``OUT_w`` of shortest paths for the current iteration and
122 scans the tree in depth first order. If an update at a vertex v cannot
123 improve any distance, the algorithm skips the entire subtree below v,
124 since none of its nodes can produce a shorter path, as proved in [1]_.
126 Parameters
127 ----------
128 G : NetworkX graph
130 weight : string or function (default= 'weight')
131 If this is a string, then edge weights will be accessed via the
132 edge attribute with this key (that is, the weight of the edge
133 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
134 such edge attribute exists, the weight of the edge is assumed to
135 be one.
137 If this is a function, the weight of an edge is the value
138 returned by the function. The function must accept exactly three
139 positional arguments: the two endpoints of an edge and the
140 dictionary of edge attributes for that edge. The function must
141 return a number or None to indicate a hidden edge.
143 Returns
144 -------
145 predecessor, distance : dict and dict-of-dict
146 Predecessor is a dict keyed by node to the predecessor node in
147 the shortest path. The distance output is a dict keyed by source
148 node to a dict keyed by target node to the distance value of the
149 shortest path between the source and target.
151 Examples
152 --------
153 >>> G = nx.DiGraph()
154 >>> G.add_weighted_edges_from(
155 ... [
156 ... ("s", "u", 10),
157 ... ("s", "x", 5),
158 ... ("u", "v", 1),
159 ... ("u", "x", 2),
160 ... ("v", "y", 1),
161 ... ("x", "u", 3),
162 ... ("x", "v", 5),
163 ... ("x", "y", 2),
164 ... ("y", "s", 7),
165 ... ("y", "v", 6),
166 ... ]
167 ... )
168 >>> predecessors, distances = nx.floyd_warshall_tree(G)
169 >>> nx.reconstruct_path("s", "v", predecessors)
170 ['s', 'x', 'u', 'v']
172 Notes
173 -----
174 Floyd's algorithm is appropriate for finding shortest paths
175 in dense graphs or graphs with negative weights when Dijkstra's algorithm
176 fails. This algorithm can still fail if there are negative cycles.
177 It has worst case running time $O(|V|^3)$ with running space of $O(|V|^2)$.
179 For complete directed graphs with independent edge weights drawn from the
180 uniform distribution on [0, 1], the expected running time is
181 $O(|V|^2 (\log |V|)^2)$, as shown in [1]_.
183 See Also
184 --------
185 floyd_warshall_predecessor_and_distance
186 floyd_warshall
187 floyd_warshall_numpy
189 References
190 ----------
191 .. [1] Brodnik, Andrej, Marko Grgurovic, and Rok Pozar.
192 "Modifications of the Floyd-Warshall algorithm with
193 nearly quadratic expected-time."
194 Ars Math. Contemp. 22, no. 1 (2022).
195 https://doi.org/10.26493/1855-3974.2467.497
196 """
197 inf = float("inf")
198 pred, dist = _init_pred_dist(G, weight)
200 # dont check for those w, `from` which `no` path exists
201 for w, pred_w in pred.items():
202 # out_w will store the adjacency list of the OUT_W tree of the paper,
203 # it is a tree, parent --> list of children
204 out_w = {parent: [] for parent in G}
205 for v, parent in pred_w.items(): # w to v path exist
206 if v == w:
207 continue
208 out_w[parent].append(v)
210 # dfs order dict and skip dict in practical improvements in the paper
211 stack = [w]
212 dfs_dict = {} # {node: next node in dfs order}
213 skip_dict = {} # {node: next node after subtree is skipped}
215 node = None
216 while stack:
217 next_node = stack.pop()
218 dfs_dict[node] = next_node
219 if stack:
220 skip_dict[next_node] = stack[-1]
221 stack.extend(out_w[next_node])
222 node = next_node
224 dist_w = dist[w] # for speed
225 # main inner loop starts here
226 for u in G:
227 if u == w: # small optimization
228 continue
229 dist_u = dist[u]
230 dist_uw = dist_u[w]
231 if dist_uw == inf: # small optimization
232 continue
234 # note: we skip v=w as relaxation would always fail
235 v = dfs_dict[w]
236 while v is not None:
237 dist_uwv = dist_uw + dist_w[v]
238 if dist_u[v] > dist_uwv:
239 dist_u[v] = dist_uwv
240 # update/new entries to be created in pred[u]
241 pred[u][v] = pred_w[v] # v must be in pred_w as checked above
242 v = dfs_dict.get(v, None)
243 else:
244 v = skip_dict.get(v, None)
246 return dict(pred), dict(dist)
249@nx._dispatchable(edge_attrs="weight")
250def floyd_warshall_predecessor_and_distance(G, weight="weight"):
251 """Find all-pairs shortest path lengths using Floyd's algorithm.
253 Parameters
254 ----------
255 G : NetworkX graph
257 weight : string or function (default= 'weight')
258 If this is a string, then edge weights will be accessed via the
259 edge attribute with this key (that is, the weight of the edge
260 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
261 such edge attribute exists, the weight of the edge is assumed to
262 be one.
264 If this is a function, the weight of an edge is the value
265 returned by the function. The function must accept exactly three
266 positional arguments: the two endpoints of an edge and the
267 dictionary of edge attributes for that edge. The function must
268 return a number or None to indicate a hidden edge.
270 Returns
271 -------
272 predecessor,distance : dictionaries
273 Dictionaries, keyed by source and target, of predecessors and distances
274 in the shortest path.
276 Examples
277 --------
278 >>> G = nx.DiGraph()
279 >>> G.add_weighted_edges_from(
280 ... [
281 ... ("s", "u", 10),
282 ... ("s", "x", 5),
283 ... ("u", "v", 1),
284 ... ("u", "x", 2),
285 ... ("v", "y", 1),
286 ... ("x", "u", 3),
287 ... ("x", "v", 5),
288 ... ("x", "y", 2),
289 ... ("y", "s", 7),
290 ... ("y", "v", 6),
291 ... ]
292 ... )
293 >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
294 >>> print(nx.reconstruct_path("s", "v", predecessors))
295 ['s', 'x', 'u', 'v']
297 Notes
298 -----
299 Floyd's algorithm is appropriate for finding shortest paths
300 in dense graphs or graphs with negative weights when Dijkstra's algorithm
301 fails. This algorithm can still fail if there are negative cycles.
302 It has running time $O(n^3)$ with running space of $O(n^2)$.
304 See Also
305 --------
306 floyd_warshall
307 floyd_warshall_numpy
308 all_pairs_shortest_path
309 all_pairs_shortest_path_length
310 """
311 pred, dist = _init_pred_dist(G, weight)
312 for w in G:
313 dist_w = dist[w] # save recomputation
314 for u in G:
315 dist_u = dist[u] # save recomputation
316 for v in G:
317 d = dist_u[w] + dist_w[v]
318 if dist_u[v] > d:
319 dist_u[v] = d
320 pred[u][v] = pred[w][v]
321 return dict(pred), dict(dist)
324@nx._dispatchable(graphs=None)
325def reconstruct_path(source, target, predecessors):
326 """Reconstruct a path from source to target using the predecessors
327 dict as returned by floyd_warshall_predecessor_and_distance
329 Parameters
330 ----------
331 source : node
332 Starting node for path
334 target : node
335 Ending node for path
337 predecessors: dictionary
338 Dictionary, keyed by source and target, of predecessors in the
339 shortest path, as returned by floyd_warshall_predecessor_and_distance
341 Returns
342 -------
343 path : list
344 A list of nodes containing the shortest path from source to target
346 If source and target are the same, an empty list is returned
348 Notes
349 -----
350 This function is meant to give more applicability to the
351 floyd_warshall_predecessor_and_distance function
353 See Also
354 --------
355 floyd_warshall_predecessor_and_distance
356 """
357 if source == target:
358 return []
359 prev = predecessors[source]
360 curr = prev[target]
361 path = [target, curr]
362 while curr != source:
363 curr = prev[curr]
364 path.append(curr)
365 return list(reversed(path))
368@nx._dispatchable(edge_attrs="weight")
369def floyd_warshall(G, weight="weight"):
370 """Find all-pairs shortest path lengths using Floyd's algorithm.
372 Parameters
373 ----------
374 G : NetworkX graph
376 weight : string or function (default= 'weight')
377 If this is a string, then edge weights will be accessed via the
378 edge attribute with this key (that is, the weight of the edge
379 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
380 such edge attribute exists, the weight of the edge is assumed to
381 be one.
383 If this is a function, the weight of an edge is the value
384 returned by the function. The function must accept exactly three
385 positional arguments: the two endpoints of an edge and the
386 dictionary of edge attributes for that edge. The function must
387 return a number or None to indicate a hidden edge.
390 Returns
391 -------
392 distance : dict
393 A dictionary, keyed by source and target, of shortest paths distances
394 between nodes.
396 Examples
397 --------
398 >>> from pprint import pprint
399 >>> G = nx.DiGraph()
400 >>> G.add_weighted_edges_from(
401 ... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
402 ... )
403 >>> fw = nx.floyd_warshall(G, weight="weight")
404 >>> results = {a: dict(b) for a, b in fw.items()}
405 >>> pprint(results)
406 {0: {0: 0, 1: 5, 2: 7, 3: 4},
407 1: {0: inf, 1: 0, 2: 2, 3: -1},
408 2: {0: inf, 1: inf, 2: 0, 3: -3},
409 3: {0: inf, 1: inf, 2: 8, 3: 0}}
411 Notes
412 -----
413 Floyd's algorithm is appropriate for finding shortest paths
414 in dense graphs or graphs with negative weights when Dijkstra's algorithm
415 fails. This algorithm can still fail if there are negative cycles.
416 It has running time $O(n^3)$ with running space of $O(n^2)$.
418 See Also
419 --------
420 floyd_warshall_predecessor_and_distance
421 floyd_warshall_numpy
422 all_pairs_shortest_path
423 all_pairs_shortest_path_length
424 """
425 # could make this its own function to reduce memory costs
426 return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]