拓扑图的加权(权值有负值)最短路径以及边介数的计算python
时间: 2024-04-28 07:14:14 浏览: 9
拓扑图的加权最短路径可以使用Dijkstra算法或Bellman-Ford算法实现,而边介数可以使用Brandes算法实现。
以下是使用Python实现Dijkstra算法和Brandes算法的示例代码:
```python
# Dijkstra算法
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph} # 起点到各点的距离,默认无限大
dist[start] = 0 # 起点到自身距离为0
visited = set() # 已访问的节点
while len(visited) < len(graph):
node = min(set(dist.keys()) - visited, key=dist.get) # 未访问的节点中距离最短的节点
visited.add(node)
for neighbor, weight in graph[node].items():
newdist = dist[node] + weight
if newdist < dist[neighbor]:
dist[neighbor] = newdist
return dist
# Brandes算法
def brandes(graph):
betweenness = {node: 0.0 for node in graph} # 节点介数初始化为0
for node in graph:
stack = []
pred = {v: [] for v in graph}
sigma = {v: 0.0 for v in graph}
sigma[node] = 1.0
dist = {v: -1 for v in graph}
dist[node] = 0
queue = [node]
while queue:
v = queue.pop(0)
stack.append(v)
for w in graph[v]:
if dist[w] < 0:
queue.append(w)
dist[w] = dist[v] + 1
if dist[w] == dist[v] + 1:
sigma[w] += sigma[v]
pred[w].append(v)
delta = {v: 0.0 for v in graph}
while stack:
w = stack.pop()
for v in pred[w]:
delta[v] += (sigma[v]/sigma[w]) * (1 + delta[w])
if w != node:
betweenness[w] += delta[w]
return betweenness
```
其中,graph是一个字典,表示拓扑图的邻接矩阵,例如:
```python
graph = {
'A': {'B': 1, 'C': 4},
'B': {'D': 2},
'C': {'D': 3},
'D': {}
}
```
表示图中有4个节点A、B、C、D,边AB权值为1,AC权值为4,BD权值为2,CD权值为3。注意,如果两个节点之间没有边,则对应的权值为空字典。