企业官网建设流程全解析

"""
Floyd-Warshall 全源最短路径 — 三层循环 DP，O(V³)
适合稠密图，支持负权边（不含负环），附带路径重建
"""

INF = float('inf')


def floyd_warshall(graph: list) -> tuple:
"""
graph: 邻接矩阵，不连通为 INF
返回 (dist, next) 距离矩阵和路径矩阵
"""
n = len(graph)
dist = [row[:] for row in graph]
nxt = [[-1] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] != INF and i != j:
nxt[i][j] = j # 直接到达

for k in range(n): # 中间节点
for i in range(n): # 起点
for j in range(n): # 终点
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
nxt[i][j] = nxt[i][k] # 更新路径
return dist, nxt


def reconstruct_path(nxt: list, i: int, j: int) -> list:
"""重建 i 到 j 的完整路径"""
if nxt[i][j] == -1:
return []
path = [i]
while i != j:
i = nxt[i][j]
path.append(i)
return path


def transitive_closure(graph: list) -> list:
"""Warshall 算法求传递闭包 (可达性)"""
n = len(graph)
reach = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if graph[i][j] != INF:
reach[i][j] = True
for k in range(n):
for i in range(n):
for j in range(n):
if reach[i][k] and reach[k][j]:
reach[i][j] = True
return reach


def demo():
V = 4
graph = [[0, 3, INF, 7],
[8, 0, 2, INF],
[5, INF, 0, 1],
[2, INF, INF, 0]]
dist, nxt = floyd_warshall(graph)
print("距离矩阵:")
for row in dist:
print([round(x, 2) if x != INF else '∞' for x in row])
print("\n路径 0→2:", ' → '.join(map(str, reconstruct_path(nxt, 0, 2))))
tc = transitive_closure(graph)
print("传递闭包:", tc)
# 图密度
edges = sum(1 for i in range(V) for j in range(V)
if graph[i][j] not in (INF, 0))
print(f"图密度: {edges}/{V*(V-1)} = {edges/(V*(V-1))*100:.0f}%")


if __name__ == "__main__":
demo()