Практическая работа 5 по предмету : алгоритмы и структура данных

Ford Belman
def bellman_ford(graph, source):
# Step 1: Prepare the distance and predecessor for each node
distance, predecessor = dict(), dict()
for node in graph:
distance[node], predecessor[node] = float('inf'), None
distance[source] = 0

# Step 2: Relax the edges

for _ in range(len(graph) - 1):
for node in graph:
for neighbour in graph[node]:
# If the distance between the node and the neighbour is lower than the current, store it
if distance[neighbour] > distance[node] + graph[node][neighbour]:
distance[neighbour], predecessor[neighbour] = distance[node] + graph[node][neighbour], node

# Step 3: Check for negative weight cycles

for node in graph:
for neighbour in graph[node]:
assert distance[neighbour] <= distance[node] + graph[node][neighbour], "Negative weight cycle."

return distance, predecessor

if __name__ == '__main__':
graph = {
'79': {'77': 43, '35': 27, '92': 69},
'77': {'35': 87, '92': 65, '64': 71},
'64': {'35': 43, '92': 74},
'35': {'92': 49},
'92': {'50': 9},
'50': {'35': 30}
}
graph = {
'79':{'77': 43, '35': 27,'92': 69},
'77':{'35': 87,'92': 65,'64': 71},
'64':{'35': 43,'92': 74},
'35':{'92': 49},
'92':{'50': 9},
'50':{'35': 30}
}

distance, predecessor = bellman_ford(graph, source='S')

print (distance)



Floyd Warshal

def floyd_warshall(nodes,edges):

d={(u,v): float('inf') if u != v else 0 for u in nodes for v in nodes}
for (u,v), w_uv in edges.items():
d[(u,v)]=w_uv

for k in nodes:

for u in nodes:
for v in nodes:
d[(u,v)]=min(d[(u,v)], d[(u,k)] + d[(k,v)])

if any(d[(u,u)]<0 for u in nodes):

print("Grafimiz manfiy vaznli yo'naltirilgan hisoblanadi!")
return d
if __name__ == '__main__':
nodes=[79,77,35,64,92,50]
edges={
(79,77):43,
(79,35):27,
(79,92):69,
(77,35):87,
(77,92):65,
(64,77):71,
(64,35):43,
(35,50):30,
(92,35):49,
(50,92):9,
}
qisqa_yul=floyd_warshall(nodes, edges)
print(qisqa_yul)