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 if dist[u][u] < 0: # negative self loop
34 raise nx.NetworkXUnbounded("Negative cycle detected.")
35 dist[u][u] = 0
36 return pred, dist
39@nx._dispatchable(edge_attrs="weight")
40def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
41 """Find all-pairs shortest path lengths using Floyd's algorithm.
43 This algorithm for finding shortest paths takes advantage of
44 matrix representations of a graph and works well for dense
45 graphs where all-pairs shortest path lengths are desired.
46 The results are returned as a NumPy array, distance[i, j],
47 where i and j are the indexes of two nodes in nodelist.
48 The entry distance[i, j] is the distance along a shortest
49 path from i to j. If no path exists the distance is Inf.
51 Parameters
52 ----------
53 G : NetworkX graph
55 nodelist : list, optional (default=G.nodes)
56 The rows and columns are ordered by the nodes in nodelist.
57 If nodelist is None then the ordering is produced by G.nodes.
58 Nodelist should include all nodes in G.
60 weight: string, optional (default='weight')
61 Edge data key corresponding to the edge weight.
63 Returns
64 -------
65 distance : 2D numpy.ndarray
66 A numpy array of shortest path distances between nodes.
67 If there is no path between two nodes the value is Inf.
69 Examples
70 --------
71 >>> G = nx.DiGraph()
72 >>> G.add_weighted_edges_from(
73 ... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
74 ... )
75 >>> nx.floyd_warshall_numpy(G)
76 array([[ 0., 5., 7., 4.],
77 [inf, 0., 2., -1.],
78 [inf, inf, 0., -3.],
79 [inf, inf, 8., 0.]])
81 Notes
82 -----
83 Floyd's algorithm is appropriate for finding shortest paths in
84 dense graphs or graphs with negative weights when Dijkstra's
85 algorithm fails. This algorithm can still fail if there are negative
86 cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.
88 Raises
89 ------
90 NetworkXError
91 If nodelist is not a list of the nodes in G.
93 NetworkXUnbounded
94 If the (di)graph contains a negative (di)cycle, the
95 algorithm raises an exception to indicate the presence of the
96 negative (di)cycle. Note: any negative weight edge in an
97 undirected graph is a negative cycle.
98 """
99 import numpy as np
101 if nodelist is not None:
102 if not (len(nodelist) == len(G) == len(set(nodelist))):
103 raise nx.NetworkXError(
104 "nodelist must contain every node in G with no repeats."
105 "If you wanted a subgraph of G use G.subgraph(nodelist)"
106 )
108 # To handle cases when an edge has weight=0, we must make sure that
109 # nonedges are not given the value 0 as well.
110 A = nx.to_numpy_array(
111 G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
112 )
113 n, m = A.shape
114 if np.any(np.diag(A) < 0):
115 raise nx.NetworkXUnbounded("Negative cycle detected.")
116 np.fill_diagonal(A, 0) # diagonal elements should be zero
117 for i in range(n):
118 # The second term has the same shape as A due to broadcasting
119 A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
120 if np.any(np.diag(A) < 0):
121 raise nx.NetworkXUnbounded("Negative cycle detected.")
122 return A
125@nx._dispatchable(edge_attrs="weight")
126def floyd_warshall_tree(G, weight="weight"):
127 r"""Find all-pairs shortest path lengths using a Tree-based
128 modification of Floyd's algorithm.
130 This variant implements the Tree algorithm of Brodnik, Grgurovic and Pozar.
131 It differs from the classical Floyd Warshall algorithm by using a shortest
132 path tree rooted at each intermediate vertex w. For every w, the algorithm
133 builds a tree ``OUT_w`` of shortest paths for the current iteration and
134 scans the tree in depth first order. If an update at a vertex v cannot
135 improve any distance, the algorithm skips the entire subtree below v,
136 since none of its nodes can produce a shorter path, as proved in [1]_.
138 Parameters
139 ----------
140 G : NetworkX graph
142 weight : string or function (default= 'weight')
143 If this is a string, then edge weights will be accessed via the
144 edge attribute with this key (that is, the weight of the edge
145 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
146 such edge attribute exists, the weight of the edge is assumed to
147 be one.
149 If this is a function, the weight of an edge is the value
150 returned by the function. The function must accept exactly three
151 positional arguments: the two endpoints of an edge and the
152 dictionary of edge attributes for that edge. The function must
153 return a number or None to indicate a hidden edge.
155 Returns
156 -------
157 predecessor, distance : dict and dict-of-dict
158 Predecessor is a dict keyed by node to the predecessor node in
159 the shortest path. The distance output is a dict keyed by source
160 node to a dict keyed by target node to the distance value of the
161 shortest path between the source and target.
163 Raises
164 ------
165 NetworkXUnbounded
166 If the (di)graph contains a negative (di)cycle, the
167 algorithm raises an exception to indicate the presence of the
168 negative (di)cycle. Note: any negative weight edge in an
169 undirected graph is a negative cycle.
171 Examples
172 --------
173 >>> G = nx.DiGraph()
174 >>> G.add_weighted_edges_from(
175 ... [
176 ... ("s", "u", 10),
177 ... ("s", "x", 5),
178 ... ("u", "v", 1),
179 ... ("u", "x", 2),
180 ... ("v", "y", 1),
181 ... ("x", "u", 3),
182 ... ("x", "v", 5),
183 ... ("x", "y", 2),
184 ... ("y", "s", 7),
185 ... ("y", "v", 6),
186 ... ]
187 ... )
188 >>> predecessors, distances = nx.floyd_warshall_tree(G)
189 >>> nx.reconstruct_path("s", "v", predecessors)
190 ['s', 'x', 'u', 'v']
192 Notes
193 -----
194 Floyd's algorithm is appropriate for finding shortest paths
195 in dense graphs or graphs with negative weights when Dijkstra's algorithm
196 fails. This algorithm can still fail if there are negative cycles.
197 It has worst case running time $O(|V|^3)$ with running space of $O(|V|^2)$.
199 For complete directed graphs with independent edge weights drawn from the
200 uniform distribution on [0, 1], the expected running time is
201 $O(|V|^2 (\log |V|)^2)$, as shown in [1]_.
203 See Also
204 --------
205 floyd_warshall_predecessor_and_distance
206 floyd_warshall
207 floyd_warshall_numpy
209 References
210 ----------
211 .. [1] Brodnik, Andrej, Marko Grgurovic, and Rok Pozar.
212 "Modifications of the Floyd-Warshall algorithm with
213 nearly quadratic expected-time."
214 Ars Math. Contemp. 22, no. 1 (2022).
215 https://doi.org/10.26493/1855-3974.2467.497
216 """
217 inf = float("inf")
218 pred, dist = _init_pred_dist(G, weight)
220 # dont check for those w, `from` which `no` path exists
221 for w, pred_w in pred.items():
222 # out_w will store the adjacency list of the OUT_W tree of the paper,
223 # it is a tree, parent --> list of children
224 out_w = {parent: [] for parent in G}
225 for v, parent in pred_w.items(): # w to v path exist
226 if v == w:
227 continue
228 out_w[parent].append(v)
230 # dfs order dict and skip dict in practical improvements in the paper
231 stack = [w]
232 dfs_dict = {} # {node: next node in dfs order}
233 skip_dict = {} # {node: next node after subtree is skipped}
235 node = None
236 while stack:
237 next_node = stack.pop()
238 dfs_dict[node] = next_node
239 if stack:
240 skip_dict[next_node] = stack[-1]
241 stack.extend(out_w[next_node])
242 node = next_node
244 dist_w = dist[w] # for speed
245 # main inner loop starts here
246 for u in G:
247 if u == w: # small optimization
248 continue
249 dist_u = dist[u]
250 dist_uw = dist_u[w]
251 if dist_uw == inf: # small optimization
252 continue
254 # note: we skip v=w as relaxation would always fail
255 v = dfs_dict.get(w, None)
256 while v is not None:
257 dist_uwv = dist_uw + dist_w[v]
258 if dist_u[v] > dist_uwv:
259 dist_u[v] = dist_uwv
260 # update/new entries to be created in pred[u]
261 pred[u][v] = pred_w[v] # v must be in pred_w as checked above
262 v = dfs_dict.get(v, None)
263 else:
264 v = skip_dict.get(v, None)
266 if any(dist[u][u] < 0 for u in G):
267 raise nx.NetworkXUnbounded("Negative cycle detected.")
268 return dict(pred), dict(dist)
271@nx._dispatchable(edge_attrs="weight")
272def floyd_warshall_predecessor_and_distance(G, weight="weight"):
273 """Find all-pairs shortest path lengths using Floyd's algorithm.
275 Parameters
276 ----------
277 G : NetworkX graph
279 weight : string or function (default= 'weight')
280 If this is a string, then edge weights will be accessed via the
281 edge attribute with this key (that is, the weight of the edge
282 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
283 such edge attribute exists, the weight of the edge is assumed to
284 be one.
286 If this is a function, the weight of an edge is the value
287 returned by the function. The function must accept exactly three
288 positional arguments: the two endpoints of an edge and the
289 dictionary of edge attributes for that edge. The function must
290 return a number or None to indicate a hidden edge.
292 Returns
293 -------
294 predecessor,distance : dictionaries
295 Dictionaries, keyed by source and target, of predecessors and distances
296 in the shortest path.
298 Raises
299 ------
300 NetworkXUnbounded
301 If the (di)graph contains a negative (di)cycle, the
302 algorithm raises an exception to indicate the presence of the
303 negative (di)cycle. Note: any negative weight edge in an
304 undirected graph is a negative cycle.
306 Examples
307 --------
308 >>> G = nx.DiGraph()
309 >>> G.add_weighted_edges_from(
310 ... [
311 ... ("s", "u", 10),
312 ... ("s", "x", 5),
313 ... ("u", "v", 1),
314 ... ("u", "x", 2),
315 ... ("v", "y", 1),
316 ... ("x", "u", 3),
317 ... ("x", "v", 5),
318 ... ("x", "y", 2),
319 ... ("y", "s", 7),
320 ... ("y", "v", 6),
321 ... ]
322 ... )
323 >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
324 >>> print(nx.reconstruct_path("s", "v", predecessors))
325 ['s', 'x', 'u', 'v']
327 Notes
328 -----
329 Floyd's algorithm is appropriate for finding shortest paths
330 in dense graphs or graphs with negative weights when Dijkstra's algorithm
331 fails. This algorithm can still fail if there are negative cycles.
332 It has running time $O(n^3)$ with running space of $O(n^2)$.
334 See Also
335 --------
336 floyd_warshall
337 floyd_warshall_numpy
338 all_pairs_shortest_path
339 all_pairs_shortest_path_length
340 """
341 pred, dist = _init_pred_dist(G, weight)
342 for w in G:
343 dist_w = dist[w] # save recomputation
344 for u in G:
345 dist_u = dist[u] # save recomputation
346 for v in G:
347 d = dist_u[w] + dist_w[v]
348 if dist_u[v] > d:
349 dist_u[v] = d
350 pred[u][v] = pred[w][v]
351 if any(dist[u][u] < 0 for u in G):
352 raise nx.NetworkXUnbounded("Negative cycle detected.")
353 return dict(pred), dict(dist)
356@nx._dispatchable(graphs=None)
357def reconstruct_path(source, target, predecessors):
358 """Reconstruct a path from source to target using the predecessors
359 dict as returned by floyd_warshall_predecessor_and_distance
361 Parameters
362 ----------
363 source : node
364 Starting node for path
366 target : node
367 Ending node for path
369 predecessors: dictionary
370 Dictionary, keyed by source and target, of predecessors in the
371 shortest path, as returned by floyd_warshall_predecessor_and_distance
373 Returns
374 -------
375 path : list
376 A list of nodes containing the shortest path from source to target
378 If source and target are the same, an empty list is returned
380 Notes
381 -----
382 This function is meant to give more applicability to the
383 floyd_warshall_predecessor_and_distance function
385 See Also
386 --------
387 floyd_warshall_predecessor_and_distance
388 """
389 if source == target:
390 return []
391 prev = predecessors[source]
392 curr = prev[target]
393 path = [target, curr]
394 while curr != source:
395 curr = prev[curr]
396 path.append(curr)
397 return list(reversed(path))
400@nx._dispatchable(edge_attrs="weight")
401def floyd_warshall(G, weight="weight"):
402 """Find all-pairs shortest path lengths using Floyd's algorithm.
404 Parameters
405 ----------
406 G : NetworkX graph
408 weight : string or function (default= 'weight')
409 If this is a string, then edge weights will be accessed via the
410 edge attribute with this key (that is, the weight of the edge
411 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
412 such edge attribute exists, the weight of the edge is assumed to
413 be one.
415 If this is a function, the weight of an edge is the value
416 returned by the function. The function must accept exactly three
417 positional arguments: the two endpoints of an edge and the
418 dictionary of edge attributes for that edge. The function must
419 return a number or None to indicate a hidden edge.
422 Returns
423 -------
424 distance : dict
425 A dictionary, keyed by source and target, of shortest paths distances
426 between nodes.
428 Raises
429 ------
430 NetworkXUnbounded
431 If the (di)graph contains a negative (di)cycle, the
432 algorithm raises an exception to indicate the presence of the
433 negative (di)cycle. Note: any negative weight edge in an
434 undirected graph is a negative cycle.
436 Examples
437 --------
438 >>> from pprint import pprint
439 >>> G = nx.DiGraph()
440 >>> G.add_weighted_edges_from(
441 ... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
442 ... )
443 >>> fw = nx.floyd_warshall(G, weight="weight")
444 >>> results = {a: dict(b) for a, b in fw.items()}
445 >>> pprint(results)
446 {0: {0: 0, 1: 5, 2: 7, 3: 4},
447 1: {0: inf, 1: 0, 2: 2, 3: -1},
448 2: {0: inf, 1: inf, 2: 0, 3: -3},
449 3: {0: inf, 1: inf, 2: 8, 3: 0}}
451 Notes
452 -----
453 Floyd's algorithm is appropriate for finding shortest paths
454 in dense graphs or graphs with negative weights when Dijkstra's algorithm
455 fails. This algorithm can still fail if there are negative cycles.
456 It has running time $O(n^3)$ with running space of $O(n^2)$.
458 See Also
459 --------
460 floyd_warshall_predecessor_and_distance
461 floyd_warshall_numpy
462 all_pairs_shortest_path
463 all_pairs_shortest_path_length
464 """
465 # could make this its own function to reduce memory costs
466 return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]