Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/shortest_paths/dense.py: 19%
53 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Floyd-Warshall algorithm for shortest paths.
2"""
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._dispatch(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([(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)])
47 >>> nx.floyd_warshall_numpy(G)
48 array([[ 0., 5., 7., 4.],
49 [inf, 0., 2., -1.],
50 [inf, inf, 0., -3.],
51 [inf, inf, 8., 0.]])
53 Notes
54 -----
55 Floyd's algorithm is appropriate for finding shortest paths in
56 dense graphs or graphs with negative weights when Dijkstra's
57 algorithm fails. This algorithm can still fail if there are negative
58 cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.
60 Raises
61 ------
62 NetworkXError
63 If nodelist is not a list of the nodes in G.
64 """
65 import numpy as np
67 if nodelist is not None:
68 if not (len(nodelist) == len(G) == len(set(nodelist))):
69 raise nx.NetworkXError(
70 "nodelist must contain every node in G with no repeats."
71 "If you wanted a subgraph of G use G.subgraph(nodelist)"
72 )
74 # To handle cases when an edge has weight=0, we must make sure that
75 # nonedges are not given the value 0 as well.
76 A = nx.to_numpy_array(
77 G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
78 )
79 n, m = A.shape
80 np.fill_diagonal(A, 0) # diagonal elements should be zero
81 for i in range(n):
82 # The second term has the same shape as A due to broadcasting
83 A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
84 return A
87@nx._dispatch(edge_attrs="weight")
88def floyd_warshall_predecessor_and_distance(G, weight="weight"):
89 """Find all-pairs shortest path lengths using Floyd's algorithm.
91 Parameters
92 ----------
93 G : NetworkX graph
95 weight: string, optional (default= 'weight')
96 Edge data key corresponding to the edge weight.
98 Returns
99 -------
100 predecessor,distance : dictionaries
101 Dictionaries, keyed by source and target, of predecessors and distances
102 in the shortest path.
104 Examples
105 --------
106 >>> G = nx.DiGraph()
107 >>> G.add_weighted_edges_from(
108 ... [
109 ... ("s", "u", 10),
110 ... ("s", "x", 5),
111 ... ("u", "v", 1),
112 ... ("u", "x", 2),
113 ... ("v", "y", 1),
114 ... ("x", "u", 3),
115 ... ("x", "v", 5),
116 ... ("x", "y", 2),
117 ... ("y", "s", 7),
118 ... ("y", "v", 6),
119 ... ]
120 ... )
121 >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
122 >>> print(nx.reconstruct_path("s", "v", predecessors))
123 ['s', 'x', 'u', 'v']
125 Notes
126 -----
127 Floyd's algorithm is appropriate for finding shortest paths
128 in dense graphs or graphs with negative weights when Dijkstra's algorithm
129 fails. This algorithm can still fail if there are negative cycles.
130 It has running time $O(n^3)$ with running space of $O(n^2)$.
132 See Also
133 --------
134 floyd_warshall
135 floyd_warshall_numpy
136 all_pairs_shortest_path
137 all_pairs_shortest_path_length
138 """
139 from collections import defaultdict
141 # dictionary-of-dictionaries representation for dist and pred
142 # use some defaultdict magick here
143 # for dist the default is the floating point inf value
144 dist = defaultdict(lambda: defaultdict(lambda: float("inf")))
145 for u in G:
146 dist[u][u] = 0
147 pred = defaultdict(dict)
148 # initialize path distance dictionary to be the adjacency matrix
149 # also set the distance to self to 0 (zero diagonal)
150 undirected = not G.is_directed()
151 for u, v, d in G.edges(data=True):
152 e_weight = d.get(weight, 1.0)
153 dist[u][v] = min(e_weight, dist[u][v])
154 pred[u][v] = u
155 if undirected:
156 dist[v][u] = min(e_weight, dist[v][u])
157 pred[v][u] = v
158 for w in G:
159 dist_w = dist[w] # save recomputation
160 for u in G:
161 dist_u = dist[u] # save recomputation
162 for v in G:
163 d = dist_u[w] + dist_w[v]
164 if dist_u[v] > d:
165 dist_u[v] = d
166 pred[u][v] = pred[w][v]
167 return dict(pred), dict(dist)
170@nx._dispatch(graphs=None)
171def reconstruct_path(source, target, predecessors):
172 """Reconstruct a path from source to target using the predecessors
173 dict as returned by floyd_warshall_predecessor_and_distance
175 Parameters
176 ----------
177 source : node
178 Starting node for path
180 target : node
181 Ending node for path
183 predecessors: dictionary
184 Dictionary, keyed by source and target, of predecessors in the
185 shortest path, as returned by floyd_warshall_predecessor_and_distance
187 Returns
188 -------
189 path : list
190 A list of nodes containing the shortest path from source to target
192 If source and target are the same, an empty list is returned
194 Notes
195 -----
196 This function is meant to give more applicability to the
197 floyd_warshall_predecessor_and_distance function
199 See Also
200 --------
201 floyd_warshall_predecessor_and_distance
202 """
203 if source == target:
204 return []
205 prev = predecessors[source]
206 curr = prev[target]
207 path = [target, curr]
208 while curr != source:
209 curr = prev[curr]
210 path.append(curr)
211 return list(reversed(path))
214@nx._dispatch(edge_attrs="weight")
215def floyd_warshall(G, weight="weight"):
216 """Find all-pairs shortest path lengths using Floyd's algorithm.
218 Parameters
219 ----------
220 G : NetworkX graph
222 weight: string, optional (default= 'weight')
223 Edge data key corresponding to the edge weight.
226 Returns
227 -------
228 distance : dict
229 A dictionary, keyed by source and target, of shortest paths distances
230 between nodes.
232 Examples
233 --------
234 >>> G = nx.DiGraph()
235 >>> G.add_weighted_edges_from([(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)])
236 >>> fw = nx.floyd_warshall(G, weight='weight')
237 >>> results = {a: dict(b) for a, b in fw.items()}
238 >>> print(results)
239 {0: {0: 0, 1: 5, 2: 7, 3: 4}, 1: {1: 0, 2: 2, 3: -1, 0: inf}, 2: {2: 0, 3: -3, 0: inf, 1: inf}, 3: {3: 0, 2: 8, 0: inf, 1: inf}}
241 Notes
242 -----
243 Floyd's algorithm is appropriate for finding shortest paths
244 in dense graphs or graphs with negative weights when Dijkstra's algorithm
245 fails. This algorithm can still fail if there are negative cycles.
246 It has running time $O(n^3)$ with running space of $O(n^2)$.
248 See Also
249 --------
250 floyd_warshall_predecessor_and_distance
251 floyd_warshall_numpy
252 all_pairs_shortest_path
253 all_pairs_shortest_path_length
254 """
255 # could make this its own function to reduce memory costs
256 return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]