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

可以使用Floyd算法计算无权无向网络中所有节点对之间的最短路径，并统计路径的数量。以下是一个Python实现的示例代码：

INF = float('inf')

def floyd(graph):
    n = len(graph)
    dist = [[INF] * n for _ in range(n)]
    count = [[0] * n for _ in range(n)]
    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
            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]

    return dist, count

if __name__ == '__main__':
    graph = [[0, 1, 1, 0],
             [1, 0, 1, 1],
             [1, 1, 0, 1],
             [0, 1, 1, 0]]
    dist, count = floyd(graph)
    for i in range(len(dist)):
        for j in range(i+1, len(dist)):
            print(f"The number of shortest paths from {i} to {j} is {count[i][j]}")

输出结果为：

The number of shortest paths from 0 to 1 is 1
The number of shortest paths from 0 to 2 is 1
The number of shortest paths from 0 to 3 is 2
The number of shortest paths from 1 to 2 is 1
The number of shortest paths from 1 to 3 is 1
The number of shortest paths from 2 to 3 is 1

在上面的示例中，我们使用了一个邻接矩阵表示无权无向网络，其中0表示节点之间没有边。`floyd`函数返回一个二维数组`dist`，其中`dist[i][j]`表示节点i到节点j的最短路径长度，以及一个二维数组`count`，其中`count[i][j]`表示节点i到节点j的最短路径数量。在计算最短路径时，我们利用一个二维数组`count`来记录路径数量，若存在新的最短路径，则将路径数量更新为经过该路径的两个节点之间路径数量的乘积。最后，我们遍历所有节点对，输出它们之间的最短路径数量即可。