我正在尝试使用 https://en.wikipedia.org/wiki/Seidel%27s_algorithm 中的 python 程序.
from numpy import matrix
def apd(A, n: int):
"""Compute the shortest-paths lengths."""
if all(print(i,j)or A[i][j] for i in range(n) for j in range(n) if i != j):
return A
Z=A**2
B=matrix([[1 if i != j and (A[i][j] == 1 or Z[i][j] > 0) else 0 for j in range(n)]for i in range(n)])
T=apd(B,n)
X = T*A
degree = [sum(A[i][j] for j in range(n)) for i in range(n)]
D = matrix([[2 * T[i][j] if X[i][j] >= T[i][j] * degree[j] else 2 * T[i][j] - 1 for j in range(n)]for i in range(n)])
return D
maatriks=matrix([
[0,0,1,0,0],
[0,0,1,0,1],
[1,1,0,1,1],
[0,0,1,0,0],
[0,1,1,0,0]])
print(apd(maatriks,5))
但是我给出了错误:
Traceback (most recent call last):
File "[PATH]/Seidel.py", line 19, in <module>
print(apd(maatriks,5))
File "[PATH]/Seidel.py", line 4, in apd
if all(print(i,j)or A[i][j] for i in range(n) for j in range(n) if i != j):
File "[PATH]/Seidel.py", line 4, in <genexpr>
if all(print(i,j)or A[i][j] for i in range(n) for j in range(n) if i != j):
File "/usr/local/lib/python3.8/dist-packages/numpy/matrixlib/defmatrix.py", line 193, in __getitem__
out = N.ndarray.__getitem__(self, index)
IndexError: index 1 is out of bounds for axis 0 with size 1
是我错误地使用了该程序还是该程序本身不正确? Here第 9 页上的算法似乎与 Python 中实现的算法完全相同。
最佳答案
这个实现对我有用。维基百科上提供的代码索引不正确。当索引 numpy 矩阵以获得第 i'th 、 j'th 元素时,您需要执行 A[i,j]
而不是 A[i][j]
from numpy import matrix
def apd(A, n: int):
"""Compute the shortest-paths lengths."""
if all(A[i, j] for i in range(n) for j in range(n) if i != j):
return A
Z = A ** 2
B = matrix(
[
[1 if i != j and (A[i, j] == 1 or Z[i, j] > 0) else 0 for j in range(n)]
for i in range(n)
]
)
T = apd(B, n)
X = T * A
degree = [sum(A[i, j] for j in range(n)) for i in range(n)]
D = matrix(
[
[
2 * T[i, j] if X[i, j] >= T[i, j] * degree[j] else 2 * T[i, j] - 1
for j in range(n)
]
for i in range(n)
]
)
return D
a = matrix(
[
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 1],
[1, 1, 0, 1, 1],
[0, 0, 1, 0, 0],
[0, 1, 1, 0, 0],
]
)
print(apd(a, 5))
返回此。
[[0 2 1 2 2]
[2 0 1 2 1]
[1 1 0 1 1]
[2 2 1 0 2]
[2 1 1 2 0]]
这是您期望看到的回应吗?
关于python - 维基百科页面上的塞德尔算法是否不正确?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/67437377/