有向加权图（权值存在负数）求最短路径的边介数python实现

以下是Python实现有向加权图最短路径的边介数的示例代码：

import heapq

def shortest_path_edge_betweenness(G, s, t):
    # 初始化边介数和距离
    betweenness = {(u, v): 0.0 for u in G for v in G[u]}
    distance = {u: float('inf') for u in G}
    distance[s] = 0.0
    paths = {u: [] for u in G}
    paths[s] = [[s]]

    # 计算最短路径和路径数量
    queue = [(0.0, s, None)]
    while queue:
        (dist, u, p) = heapq.heappop(queue)
        for v, e in G[u].items():
            w = e['weight']
            if distance[v] > dist + w:
                distance[v] = dist + w
                paths[v] = [path + [v] for path in paths[u]]
                heapq.heappush(queue, (distance[v], v, u))
            elif distance[v] == dist + w:
                paths[v].extend([path + [v] for path in paths[u]])

    # 计算边介数
    credit = {u: 1.0 for u in G}
    while paths[t]:
        path = paths[t].pop()
        for i in range(len(path) - 1):
            u, v = path[i], path[i + 1]
            credit[v] += credit[u] * betweenness[(u, v)]
            betweenness[(u, v)] += credit[u] / credit[v]

    return betweenness

该算法使用Dijkstra算法计算最短路径和路径数量，并通过迭代计算边介数。该算法的时间复杂度为$O(mn\log n)$，其中$m$是边数，$n$是节点数。