有向加权图求最短路径及边介数

最短路径可以使用Dijkstra算法或Bellman-Ford算法求解。

1. Dijkstra算法

Dijkstra算法适用于边权为非负数的图，可以求出单源最短路径。

具体步骤：

- 初始化：将起点的距离设置为0，其他点的距离设置为无穷大。
- 选取最短距离的点：从未确定最短路径的点中选取距离最短的点作为当前点。
- 更新距离：遍历当前点的邻居节点，更新其距离（如果通过当前点到达邻居节点的距离比已知的距离更短）。
- 标记已确定的最短距离：将当前点标记为已确定最短距离。
- 重复上述步骤，直到所有点的最短路径都被确定。

2. Bellman-Ford算法

Bellman-Ford算法可以处理边权为任意实数的图，可以检测负权环。

具体步骤：

- 初始化：将起点的距离设置为0，其他点的距离设置为无穷大。
- 松弛操作：遍历所有边，如果通过一条边到达目标节点的距离比已知的距离更短，更新目标节点的距离。
- 检测负权环：重复执行第2步，直到没有节点的距离再发生变化或者执行了节点数次松弛操作。如果还有节点的距离可以被更新，说明存在负权环。

边介数可以使用Brandes算法求解。

Brandes算法适用于有向图和无向图，可以计算任意节点对之间的边介数。

具体步骤：

- 初始化：对于每个节点v，将其介数值设为0。
- 遍历所有节点：对于每个节点s，执行下列步骤：
- 初始化：对于每个节点v，将其距离d设为无穷大，最短路径数sigma设为0，前驱节点列表P为空。
- 设置起点的距离为0，最短路径数为1。
- 使用Dijkstra算法计算出从起点s到所有其他节点的最短路径，并记录每个节点v的距离d和最短路径数sigma。
- 使用反向遍历，计算从s出发经过每个节点v的最短路径条数，并将其累加到v的介数值中。
- 标准化：对于每个节点v，将其介数值除以2。

参考代码：

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    visited = set()
    while len(visited) < len(graph):
        v = min((d, v) for (v, d) in dist.items() if v not in visited)[1]
        visited.add(v)
        for w, d in graph[v]:
            if dist[v] + d < dist[w]:
                dist[w] = dist[v] + d
    return dist

def brandes(graph):
    b = {v: 0 for v in graph}
    for s in graph:
        dist = dijkstra(graph, s)
        sigma = {v: 0 for v in graph}
        sigma[s] = 1
        P = {v: [] for v in graph}
        for t in sorted(graph, key=dist.get):
            for w, d in graph[t]:
                if dist[t] + d == dist[w]:
                    sigma[w] += sigma[t]
                    P[w].append(t)
        delta = {v: 0 for v in graph}
        while P:
            w = P.popitem()[0]
            for v in P[w]:
                delta[v] += sigma[v] / sigma[w] * (1 + delta[w])
            if w != s:
                b[w] += delta[w] / 2
    return b