负权有向图的多条最短路径计算，依据最短路径进行边介数的计算python实现

以下是一个基于Dijkstra算法的负权有向图多条最短路径计算的Python实现：

import heapq

def dijkstra(graph, start):
    # 初始化距离和前驱字典
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    
    # 初始化堆和visited集合
    heap = [(0, start)]
    visited = set()
    
    while heap:
        # 取出堆顶节点并标记为visited
        (curr_dist, curr_node) = heapq.heappop(heap)
        visited.add(curr_node)
        
        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[curr_node].items():
            if neighbor not in visited:
                # 更新邻居节点的距离和前驱
                new_dist = dist[curr_node] + weight
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    prev[neighbor] = curr_node
                    heapq.heappush(heap, (new_dist, neighbor))
    
    return dist, prev

def get_shortest_paths(graph, start, end, num_paths):
    # 使用Dijkstra算法计算最短路径
    dist, prev = dijkstra(graph, start)
    
    # 初始化结果列表和堆
    paths = []
    heap = [(dist[end], [end])]
    
    while heap and len(paths) < num_paths:
        # 取出堆顶路径
        (curr_dist, curr_path) = heapq.heappop(heap)
        
        # 如果当前路径的最后一个节点就是目标节点，加入结果列表
        if curr_path[-1] == start:
            paths.append(curr_path[::-1])
        else:
            # 遍历当前路径的前驱节点
            for prev_node in graph[curr_path[-1]]:
                if prev_node not in curr_path:
                    # 创建新路径并加入堆
                    new_path = curr_path + [prev_node]
                    new_dist = curr_dist - graph[curr_path[-1]][prev_node]
                    heapq.heappush(heap, (new_dist, new_path))
    
    return paths

def calculate_betweenness(graph):
    # 初始化边介数字典
    betweenness = {edge: 0 for edge in graph.edges()}
    
    # 遍历所有节点对
    for node in graph:
        for path in get_shortest_paths(graph, node, node, len(graph)):
            # 遍历路径上的所有边，更新边介数
            for i in range(len(path)-1):
                edge = (path[i], path[i+1])
                betweenness[edge] += 1
    
    # 对所有边介数进行归一化
    total_paths = len(graph) * (len(graph) - 1)
    for edge in betweenness:
        betweenness[edge] /= 2 * total_paths
    
    return betweenness

这个实现中，首先使用Dijkstra算法计算出起点到每个节点的最短距离和前驱节点。然后使用堆和visited集合，遍历所有从起点到终点的路径，并按照距离从小到大加入堆中。每次取出堆顶路径，如果路径的最后一个节点是终点，就将该路径加入结果列表。否则，遍历该路径的最后一个节点的前驱节点，创建新路径并加入堆中。最后，遍历所有路径上的边，更新边介数。

注意，这个实现中的边介数是基于无向图的，因此对于有向图中的每条边，需要将它的方向分别计算一次，然后将两个方向的结果相加。