"""弗洛伊德-沃舍尔算法用于最短路径。"""
import networkx as nx
__all__ = [
"floyd_warshall",
"floyd_warshall_predecessor_and_distance",
"reconstruct_path",
"floyd_warshall_numpy",
]
[docs]
@nx._dispatchable(edge_attrs="weight")
def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
"""使用Floyd算法查找所有节点对之间的最短路径长度。
该算法利用图的矩阵表示法，适用于密集图，其中需要所有节点对之间的最短路径长度。结果以NumPy数组形式返回，distance[i, j]，其中i和j是nodelist中两个节点的索引。distance[i, j]表示从i到j的最短路径距离。如果不存在路径，则距离为Inf。
Parameters
----------
G : NetworkX图
nodelist : 列表, 可选 (默认=G.nodes)
行和列按nodelist中的节点排序。如果nodelist为None，则按G.nodes生成排序。Nodelist应包含G中的所有节点。
weight: 字符串, 可选 (默认='weight')
对应边权重的边数据键。
Returns
-------
distance : 2D numpy.ndarray
一个包含节点间最短路径距离的NumPy数组。如果两个节点之间没有路径，则值为Inf。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
... )
>>> nx.floyd_warshall_numpy(G)
array([[ 0., 5., 7., 4.],
[inf, 0., 2., -1.],
[inf, inf, 0., -3.],
[inf, inf, 8., 0.]])
Notes
-----
Floyd算法适用于在密集图或具有负权重的图中查找最短路径，当Dijkstra算法失败时。如果存在负环，该算法仍可能失败。其运行时间为$O(n^3)$，运行空间为$O(n^2)$。
Raises
------
NetworkXError
如果nodelist不是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, multigraph_weight=min, weight=weight, nonedge=np.inf
)
n, m = A.shape
np.fill_diagonal(A, 0) # diagonal elements should be zero
for i in range(n):
# The second term has the same shape as A due to broadcasting
A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
return A
[docs]
@nx._dispatchable(edge_attrs="weight")
def floyd_warshall_predecessor_and_distance(G, weight="weight"):
"""使用Floyd算法查找所有节点对之间的最短路径长度。
Parameters
----------
G : NetworkX图
weight: 字符串, 可选 (默认= 'weight')
对应边权重的边数据键。
Returns
-------
predecessor, distance : 字典
以源节点和目标节点为键的字典，包含最短路径中的前驱节点和距离。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
... [
... ("s", "u", 10),
... ("s", "x", 5),
... ("u", "v", 1),
... ("u", "x", 2),
... ("v", "y", 1),
... ("x", "u", 3),
... ("x", "v", 5),
... ("x", "y", 2),
... ("y", "s", 7),
... ("y", "v", 6),
... ]
... )
>>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
>>> print(nx.reconstruct_path("s", "v", predecessors))
['s', 'x', 'u', 'v']
Notes
-----
Floyd算法适用于在密集图或具有负权重的图中查找最短路径，当Dijkstra算法失效时。如果存在负环，此算法仍可能失败。
它的时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$。
See Also
--------
floyd_warshall
floyd_warshall_numpy
all_pairs_shortest_path
all_pairs_shortest_path_length
"""
from collections import defaultdict
# dictionary-of-dictionaries representation for dist and pred
# use some defaultdict magick here
# for dist the default is the floating point inf value
dist = defaultdict(lambda: defaultdict(lambda: float("inf")))
for u in G:
dist[u][u] = 0
pred = defaultdict(dict)
# initialize path distance dictionary to be the adjacency matrix
# also set the distance to self to 0 (zero diagonal)
undirected = not G.is_directed()
for u, v, d in G.edges(data=True):
e_weight = d.get(weight, 1.0)
dist[u][v] = min(e_weight, dist[u][v])
pred[u][v] = u
if undirected:
dist[v][u] = min(e_weight, dist[v][u])
pred[v][u] = v
for w in G:
dist_w = dist[w] # save recomputation
for u in G:
dist_u = dist[u] # save recomputation
for v in G:
d = dist_u[w] + dist_w[v]
if dist_u[v] > d:
dist_u[v] = d
pred[u][v] = pred[w][v]
return dict(pred), dict(dist)
[docs]
@nx._dispatchable(graphs=None)
def reconstruct_path(source, target, predecessors):
"""使用前驱字典从源到目标重构路径，如floyd_warshall_predecessor_and_distance函数返回的那样
Parameters
----------
source : 节点
路径的起始节点
target : 节点
路径的结束节点
predecessors: 字典
一个字典，以源和目标为键，记录最短路径中的前驱节点，如floyd_warshall_predecessor_and_distance函数返回的那样
Returns
-------
path : 列表
一个包含从源到目标的最短路径的节点列表
如果源和目标相同，则返回一个空列表
Notes
-----
此函数旨在增加floyd_warshall_predecessor_and_distance函数的适用性
See Also
--------
floyd_warshall_predecessor_and_distance
"""
if source == target:
return []
prev = predecessors[source]
curr = prev[target]
path = [target, curr]
while curr != source:
curr = prev[curr]
path.append(curr)
return list(reversed(path))
[docs]
@nx._dispatchable(edge_attrs="weight")
def floyd_warshall(G, weight="weight"):
"""使用Floyd算法查找所有节点对之间的最短路径长度。
Parameters
----------
G : NetworkX图
weight: 字符串, 可选 (默认= 'weight')
对应边权重的边数据键。
Returns
-------
distance : 字典
一个字典，键为源节点和目标节点，值为节点间的最短路径距离。
Examples
--------
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
... [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
... )
>>> fw = nx.floyd_warshall(G, weight="weight")
>>> results = {a: dict(b) for a, b in fw.items()}
>>> print(results)
{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}}
Notes
-----
Floyd算法适用于在密集图或具有负权重的图中查找最短路径，当Dijkstra算法失效时。如果存在负权重环，该算法仍然可能失败。它的时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$。
See Also
--------
floyd_warshall_predecessor_and_distance
floyd_warshall_numpy
all_pairs_shortest_path
all_pairs_shortest_path_length
"""
# could make this its own function to reduce memory costs
return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]
