高效的网络优化算法源代码 - Kruskal、Prim、Dijkstra 等
对于网络优化问题，有许多不同的算法可以解决。以下是一些常见的高效网络优化算法及其源代码：
- 最小生成树（MST）算法：Kruskal、Prim
Kruskal算法：
def kruskal(graph):
parent = {}
rank = {}
def make_set(node):
parent[node] = node
rank[node] = 0
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(node1, node2):
root1 = find(node1)
root2 = find(node2)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
for node in graph['vertices']:
make_set(node)
minimum_spanning_tree = set()
edges = list(graph['edges'])
edges.sort()
for edge in edges:
weight, node1, node2 = edge
if find(node1) != find(node2):
union(node1, node2)
minimum_spanning_tree.add(edge)
return minimum_spanning_tree
Prim算法：
import heapq
def prim(graph, start_node):
visited = set()
heap = [(0, start_node)]
minimum_spanning_tree = set()
while heap:
(weight, current_node) = heapq.heappop(heap)
if current_node not in visited:
visited.add(current_node)
minimum_spanning_tree.add((weight, current_node))
for neighbor, neighbor_weight in graph[current_node].items():
if neighbor not in visited:
heapq.heappush(heap, (neighbor_weight, neighbor))
return minimum_spanning_tree
- 最短路径算法：Dijkstra、Bellman-Ford、Floyd-Warshall
Dijkstra算法：
import heapq
def dijkstra(graph, start_node):
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
heap = [(0, start_node)]
while heap:
(current_distance, current_node) = heapq.heappop(heap)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
Bellman-Ford算法：
def bellman_ford(graph, start_node):
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
for _ in range(len(graph) - 1):
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
# check for negative cycles
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
raise ValueError('Negative cycle detected')
return distances
Floyd-Warshall算法：
def floyd_warshall(graph):
distances = dict(graph)
for k in graph:
for i in graph:
for j in graph:
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
return distances
- 最大流算法：Ford-Fulkerson、Edmonds-Karp、Dinic
Ford-Fulkerson算法：
def ford_fulkerson(graph, source, sink):
def bfs(graph, source, sink):
visited = {node: False for node in graph}
visited[source] = True
queue = [source]
while queue:
node = queue.pop(0)
for neighbor, capacity in graph[node].items():
if not visited[neighbor] and capacity > 0:
visited[neighbor] = True
queue.append(neighbor)
if neighbor == sink:
return True
return False
flow = 0
while bfs(graph, source, sink):
path_flow = float('inf')
node = sink
while node != source:
path_flow = min(path_flow, graph[parent[node]][node])
node = parent[node]
flow += path_flow
node = sink
while node != source:
graph[parent[node]][node] -= path_flow
graph[node][parent[node]] += path_flow
node = parent[node]
return flow
Edmonds-Karp算法：
def edmonds_karp(graph, source, sink):
def bfs(graph, source, sink):
parent = {node: None for node in graph}
parent[source] = source
queue = [source]
while queue:
node = queue.pop(0)
for neighbor, capacity in graph[node].items():
if parent[neighbor] is None and capacity > 0:
parent[neighbor] = node
queue.append(neighbor)
if neighbor == sink:
return parent
return None
max_flow = 0
parent = bfs(graph, source, sink)
while parent is not None:
path_flow = float('inf')
node = sink
while node != source:
path_flow = min(path_flow, graph[parent[node]][node])
node = parent[node]
max_flow += path_flow
node = sink
while node != source:
graph[parent[node]][node] -= path_flow
graph[node][parent[node]] += path_flow
node = parent[node]
parent = bfs(graph, source, sink)
return max_flow
Dinic算法：
from collections import deque
def dinic(graph, source, sink):
def bfs(graph, source, sink, level):
queue = deque([source])
level[source] = 0
while queue:
node = queue.popleft()
for neighbor, capacity in graph[node].items():
if level[neighbor] < 0 and capacity > 0:
level[neighbor] = level[node] + 1
queue.append(neighbor)
return level[sink] >= 0
def dfs(graph, source, sink, level, blocking_flow):
if source == sink:
return blocking_flow
flow = 0
for neighbor, capacity in graph[source].items():
if level[neighbor] == level[source] + 1 and capacity > 0:
current_flow = dfs(graph, neighbor, sink, level, min(blocking_flow, capacity))
graph[source][neighbor] -= current_flow
graph[neighbor][source] += current_flow
flow += current_flow
blocking_flow -= current_flow
if blocking_flow == 0:
break
return flow
max_flow = 0
level = [-1] * (len(graph) + 1)
while bfs(graph, source, sink, level):
current_flow = dfs(graph, source, sink, level, float('inf'))
while current_flow > 0:
max_flow += current_flow
current_flow = dfs(graph, source, sink, level, float('inf'))
level = [-1] * (len(graph) + 1)
return max_flow
原文地址: https://www.cveoy.top/t/topic/nCYT 著作权归作者所有。请勿转载和采集!