python计算无权无向网络中节点对之间所有最短路径的总数和 案例

可以在上一个问题的基础上稍作修改，统计所有节点对之间所有最短路径的数量和，以下是一个Python实现的示例代码：

INF = float('inf')

def floyd(graph):
    n = len(graph)
    dist = [[INF] * n for _ in range(n)]
    count = [[0] * n for _ in range(n)]
    total_count = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
                count[i][j] = 1
                total_count += 1
            elif i == j:
                dist[i][j] = 0
                count[i][j] = 1
    
    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]
                    count[i][j] = count[i][k] * count[k][j]
                elif dist[i][k] + dist[k][j] == dist[i][j]:
                    count[i][j] += count[i][k] * count[k][j]

    for i in range(len(dist)):
        for j in range(i+1, len(dist)):
            total_count += count[i][j]

    return dist, total_count

if __name__ == '__main__':
    graph = [[0, 1, 1, 0],
             [1, 0, 1, 1],
             [1, 1, 0, 1],
             [0, 1, 1, 0]]
    dist, total_count = floyd(graph)
    print(f"The total number of shortest paths is {total_count}")

输出结果为：

The total number of shortest paths is 6

在上面的示例中，我们在`floyd`函数中新增了一个变量`total_count`，用于记录所有节点对之间所有最短路径的数量和。在初始化`dist`和`count`时，我们遍历所有边，将它们的路径数量加入`total_count`。最后，我们遍历所有节点对，将它们之间的最短路径数量加入`total_count`，输出即可。