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."""
3import networkx as nx
5__all__ = [
6 "floyd_warshall",
7 "floyd_warshall_predecessor_and_distance",
8 "reconstruct_path",
9 "floyd_warshall_numpy",
10]
13@nx._dispatchable(edge_attrs="weight")
14def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
15 """Find all-pairs shortest path lengths using Floyd's algorithm.
17 This algorithm for finding shortest paths takes advantage of
18 matrix representations of a graph and works well for dense
19 graphs where all-pairs shortest path lengths are desired.
20 The results are returned as a NumPy array, distance[i, j],
21 where i and j are the indexes of two nodes in nodelist.
22 The entry distance[i, j] is the distance along a shortest
23 path from i to j. If no path exists the distance is Inf.
25 Parameters
26 ----------
27 G : NetworkX graph
29 nodelist : list, optional (default=G.nodes)
30 The rows and columns are ordered by the nodes in nodelist.
31 If nodelist is None then the ordering is produced by G.nodes.
32 Nodelist should include all nodes in G.
34 weight: string, optional (default='weight')
35 Edge data key corresponding to the edge weight.
37 Returns
38 -------
39 distance : 2D numpy.ndarray
40 A numpy array of shortest path distances between nodes.
41 If there is no path between two nodes the value is Inf.
43 Examples
44 --------
45 >>> G = nx.DiGraph()
46 >>> G.add_weighted_edges_from(
47 ... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
48 ... )
49 >>> nx.floyd_warshall_numpy(G)
50 array([[ 0., 5., 7., 4.],
51 [inf, 0., 2., -1.],
52 [inf, inf, 0., -3.],
53 [inf, inf, 8., 0.]])
55 Notes
56 -----
57 Floyd's algorithm is appropriate for finding shortest paths in
58 dense graphs or graphs with negative weights when Dijkstra's
59 algorithm fails. This algorithm can still fail if there are negative
60 cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.
62 Raises
63 ------
64 NetworkXError
65 If nodelist is not a list of the nodes in G.
66 """
67 import numpy as np
69 if nodelist is not None:
70 if not (len(nodelist) == len(G) == len(set(nodelist))):
71 raise nx.NetworkXError(
72 "nodelist must contain every node in G with no repeats."
73 "If you wanted a subgraph of G use G.subgraph(nodelist)"
74 )
76 # To handle cases when an edge has weight=0, we must make sure that
77 # nonedges are not given the value 0 as well.
78 A = nx.to_numpy_array(
79 G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
80 )
81 n, m = A.shape
82 np.fill_diagonal(A, 0) # diagonal elements should be zero
83 for i in range(n):
84 # The second term has the same shape as A due to broadcasting
85 A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
86 return A
89@nx._dispatchable(edge_attrs="weight")
90def floyd_warshall_predecessor_and_distance(G, weight="weight"):
91 """Find all-pairs shortest path lengths using Floyd's algorithm.
93 Parameters
94 ----------
95 G : NetworkX graph
97 weight: string, optional (default= 'weight')
98 Edge data key corresponding to the edge weight.
100 Returns
101 -------
102 predecessor,distance : dictionaries
103 Dictionaries, keyed by source and target, of predecessors and distances
104 in the shortest path.
106 Examples
107 --------
108 >>> G = nx.DiGraph()
109 >>> G.add_weighted_edges_from(
110 ... [
111 ... ("s", "u", 10),
112 ... ("s", "x", 5),
113 ... ("u", "v", 1),
114 ... ("u", "x", 2),
115 ... ("v", "y", 1),
116 ... ("x", "u", 3),
117 ... ("x", "v", 5),
118 ... ("x", "y", 2),
119 ... ("y", "s", 7),
120 ... ("y", "v", 6),
121 ... ]
122 ... )
123 >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
124 >>> print(nx.reconstruct_path("s", "v", predecessors))
125 ['s', 'x', 'u', 'v']
127 Notes
128 -----
129 Floyd's algorithm is appropriate for finding shortest paths
130 in dense graphs or graphs with negative weights when Dijkstra's algorithm
131 fails. This algorithm can still fail if there are negative cycles.
132 It has running time $O(n^3)$ with running space of $O(n^2)$.
134 See Also
135 --------
136 floyd_warshall
137 floyd_warshall_numpy
138 all_pairs_shortest_path
139 all_pairs_shortest_path_length
140 """
141 from collections import defaultdict
143 # dictionary-of-dictionaries representation for dist and pred
144 # use some defaultdict magick here
145 # for dist the default is the floating point inf value
146 dist = defaultdict(lambda: defaultdict(lambda: float("inf")))
147 for u in G:
148 dist[u][u] = 0
149 pred = defaultdict(dict)
150 # initialize path distance dictionary to be the adjacency matrix
151 # also set the distance to self to 0 (zero diagonal)
152 undirected = not G.is_directed()
153 for u, v, d in G.edges(data=True):
154 e_weight = d.get(weight, 1.0)
155 dist[u][v] = min(e_weight, dist[u][v])
156 pred[u][v] = u
157 if undirected:
158 dist[v][u] = min(e_weight, dist[v][u])
159 pred[v][u] = v
160 for w in G:
161 dist_w = dist[w] # save recomputation
162 for u in G:
163 dist_u = dist[u] # save recomputation
164 for v in G:
165 d = dist_u[w] + dist_w[v]
166 if dist_u[v] > d:
167 dist_u[v] = d
168 pred[u][v] = pred[w][v]
169 return dict(pred), dict(dist)
172@nx._dispatchable(graphs=None)
173def reconstruct_path(source, target, predecessors):
174 """Reconstruct a path from source to target using the predecessors
175 dict as returned by floyd_warshall_predecessor_and_distance
177 Parameters
178 ----------
179 source : node
180 Starting node for path
182 target : node
183 Ending node for path
185 predecessors: dictionary
186 Dictionary, keyed by source and target, of predecessors in the
187 shortest path, as returned by floyd_warshall_predecessor_and_distance
189 Returns
190 -------
191 path : list
192 A list of nodes containing the shortest path from source to target
194 If source and target are the same, an empty list is returned
196 Notes
197 -----
198 This function is meant to give more applicability to the
199 floyd_warshall_predecessor_and_distance function
201 See Also
202 --------
203 floyd_warshall_predecessor_and_distance
204 """
205 if source == target:
206 return []
207 prev = predecessors[source]
208 curr = prev[target]
209 path = [target, curr]
210 while curr != source:
211 curr = prev[curr]
212 path.append(curr)
213 return list(reversed(path))
216@nx._dispatchable(edge_attrs="weight")
217def floyd_warshall(G, weight="weight"):
218 """Find all-pairs shortest path lengths using Floyd's algorithm.
220 Parameters
221 ----------
222 G : NetworkX graph
224 weight: string, optional (default= 'weight')
225 Edge data key corresponding to the edge weight.
228 Returns
229 -------
230 distance : dict
231 A dictionary, keyed by source and target, of shortest paths distances
232 between nodes.
234 Examples
235 --------
236 >>> from pprint import pprint
237 >>> G = nx.DiGraph()
238 >>> G.add_weighted_edges_from(
239 ... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
240 ... )
241 >>> fw = nx.floyd_warshall(G, weight="weight")
242 >>> results = {a: dict(b) for a, b in fw.items()}
243 >>> pprint(results)
244 {0: {0: 0, 1: 5, 2: 7, 3: 4},
245 1: {0: inf, 1: 0, 2: 2, 3: -1},
246 2: {0: inf, 1: inf, 2: 0, 3: -3},
247 3: {0: inf, 1: inf, 2: 8, 3: 0}}
249 Notes
250 -----
251 Floyd's algorithm is appropriate for finding shortest paths
252 in dense graphs or graphs with negative weights when Dijkstra's algorithm
253 fails. This algorithm can still fail if there are negative cycles.
254 It has running time $O(n^3)$ with running space of $O(n^2)$.
256 See Also
257 --------
258 floyd_warshall_predecessor_and_distance
259 floyd_warshall_numpy
260 all_pairs_shortest_path
261 all_pairs_shortest_path_length
262 """
263 # could make this its own function to reduce memory costs
264 return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]