import sys
sys.path.append('.')
sys.path.append('..')
from problem_loader import ProblemLoader
from helpers import obfuscate, process_weighted_edges
data_urls = {
'g1': 'https://d18ky98rnyall9.cloudfront.net/_6ff856efca965e8774eb18584754fd65_g1.txt?Expires=1629158400&Signature=CBTbmU3gQKTzC3D2qRdmJFj17zZVQxZzK6FZ9kosddnHq6h0R-6S5EMq0XbvIB0-ZblsswL8G79fHFkb7RTSoneZOZHkKgO5fBhT-4WhGTZHW8FddOw2BQhgM4FtpUDHUNZfur8-LvpInKbc4Re~lHVjbM6UbQdrPPignrmbXrE_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A',
'g2': 'https://d18ky98rnyall9.cloudfront.net/_6ff856efca965e8774eb18584754fd65_g2.txt?Expires=1629158400&Signature=KThsGuQL0GlFWfmj5XKKUHfOLv~gMJjaxhmzag13Nd8RCnqAMfqhwtygt9vf8R1x3C0ioYJHaNo6Fa5ESWweTGfvXiO8Nax~q2KkeeE4rrdgfzyJ34P5wYhi67dC9aoMIcdqvbL30aHTXoJfPHBgf37thIN9M3~HRz7kibIQUTc_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A',
'g3': 'https://d18ky98rnyall9.cloudfront.net/_6ff856efca965e8774eb18584754fd65_g3.txt?Expires=1629158400&Signature=LkXokerfI~OWw5HrB5M0ibMJQkK4s-sIoGN8lS1AXGRAVbKNujikuvewGWSmJhtEbvvPpnVPgzs1Pho5N4uooHivF4OGTp5QldDWjG6mhtAVV2lYr9h2LMDBKMJjeXqczQp7p65gT7bWLMEyYEt~fgkWGSDWSrromooOXy191U4_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A',
}
In this assignment you will implement one or more algorithms for the all-pairs shortest-path problem.
The first line indicates the number of vertices and edges, respectively. Each subsequent line describes an edge (the first two numbers are its tail and head, respectively) and its length (the third number).
NOTE: some of the edge lengths are negative.
NOTE: These graphs may or may not have negative-cost cycles.
Your task is to compute the "shortest shortest path". Precisely, you must first identify which, if any, of the three graphs have no negative cycles. For each such graph, you should compute all-pairs shortest paths and remember the smallest one (i.e., compute $min_{u,v\in V} d(u,v)$, where $d(u,v)$ denotes the shortest-path distance from $u$ to $v$).
If each of the three graphs has a negative-cost cycle, then enter "NULL" in the box below. If exactly one graph has no negative-cost cycles, then enter the length of its shortest shortest path in the box below. If two or more of the graphs have no negative-cost cycles, then enter the smallest of the lengths of their shortest shortest paths in the box below.
g1 = ProblemLoader(
data_urls['g1'],
fname="g1.p",
preprocessor=process_weighted_edges,
).fetch()
g2 = ProblemLoader(
data_urls['g2'],
fname="g2.p",
preprocessor=process_weighted_edges,
).fetch()
g3 = ProblemLoader(
data_urls['g3'],
fname="g3.p",
preprocessor=process_weighted_edges,
).fetch()
print(g1[0], g2[0], g3[0])
Edge(left=1, right=14, cost=6) Edge(left=1, right=2, cost=2) Edge(left=1, right=8, cost=36)
from helpers import Adjacency
def adjacency_graph_from_edges(edges):
adjacency_graph = {}
for edge in edges:
adjacency = Adjacency(to=edge.right, cost=edge.cost)
adjacency_graph[edge.left] = adjacency_graph.get(edge.left, []) + [adjacency]
adjacency_graph[edge.right] = adjacency_graph.get(edge.right, [])
return adjacency_graph
from math import inf
def distance_matrix_from_graph(graph):
""" get nxn matrix from graph, populating the cells with the cost property of each adjacency in the graph"""
matrix = [[inf] * len(graph)] * len(graph)
enumerated_values = list(enumerate(graph.keys()))
indexed_values = dict(map(reversed, enumerated_values.copy()))
for y, i in enumerated_values:
matrix[y][y] = 0
for adjacency in graph[i]:
x = indexed_values[adjacency.to]
matrix[y][x] = adjacency.cost
return matrix
def floyd_warshall(matrix):
""" return a matrix of shortest paths from the given matrix """
"""copy the matrix """
dist = list(map(lambda i: list(map(lambda j: j, i)), matrix))
l = len(matrix)
for k in range(l):
for i in range(l):
for j in range(l):
# If vertex k is on the shortest path from i to j, then update the value of dist[i][j]
dist[i][j] = min(
dist[i][j],
dist[i][k] + dist[k][j]
)
return dist
dists = []
for edges in [g1, g2, g3]:
graph = adjacency_graph_from_edges(edges)
matrix = distance_matrix_from_graph(graph)
dists.append((floyd_warshall(matrix), edges))
--------------------------------------------------------------------------- KeyboardInterrupt Traceback (most recent call last) <ipython-input-199-2b536c595ade> in <module> 3 graph = adjacency_graph_from_edges(edges) 4 matrix = distance_matrix_from_graph(graph) ----> 5 dists.append((floyd_warshall(matrix), edges)) <ipython-input-198-be696a8783a8> in floyd_warshall(matrix) 12 dist[i][j] = min( 13 dist[i][j], ---> 14 dist[i][k] + dist[k][j] 15 ) 16 return dist KeyboardInterrupt:
def get_distances(matrix, graph):
for n in range(len(matrix)):
if matrix[n][n] < 0:
return None
lengths = []
for v in graph:
for adjancency in graph[v]:
lengths.append(matrix[v][adjancency.to])
return lengths
for dist, edges in dists:
print(get_distances(dist, edges))
0 -64148769345410352274303297034163544110001088942356845484143863655692972293503142096525211048596255587897433869919540116099096282061430550351972937823416443169971629673141437263562033618808027463991148024271009944001723318603550374117612912779108242466442407311821596600319703862752957567747634834535932197585948556009419106705799797148703202356624292537542954599006930068238208483549887586926078161656383855399503894201029071575288978704737272830746740049179989423362565743827186910074346098448229522128602198943389814337157895666713981448303556593374413972034675035239382989033370910083311920519735943307891718131963607344672096668652779655776868167746539207057713083263151009110713748714551359726170156262173681919810568180251843328696766235495272163417566 None 0 -26323354712954545904590620825978203082513846225107227931473693645844981207110089316842604066128789816666249810518897960346072225258630165277399766429487718801556341343186499072382729535820727794778408532996212461629140465494583098251686249841293507339916003483238352710342859625669629476688487254498118755004596415778283757319111330296607200774480203510892866686279527080426360388766123243212410201211146201887779948416339541475318248419156011006574995005543612472622723019676466967956670441136750629342248602679848354864600068465090478763822901722954720020942449143877672484075746718803983081854543526285430813500085568713188716375282622236242883604285059708870891228973727561663360962563756043788792210537321966019715631257964999191664420051680000855387645903 None 0 -170152468923863891234781751376129647027163092522508797207162074420845934002869956067823514864258053406650728862706613649541923917673593558106805499843092497922944494637598873500854938638161473020564052322149099962575346461973800400776909925280023257161507527340059140715302348172329490595760531586514116651671441561912802076416526353523329660050403820642021250095885684632484198658929551436945149532071217898093892003838640042777683228461792750049825748643714380718313835797772234601031733095182851294756511779956652653782209946797109385275750431942508838870672309845686315359078154275895604836238433640557523153858800614331533355554524337715881707107071684479263029229052476545279681808358546031538270490887709336298349792466201965 None
Bellman-ford with added vertex connected to all others with cost 0. If negative number, stop. use the bf values to adjust the costs solve matrix of adjusted values with djistrokas revert the offset from BF
from helpers import Edge
def bellman_ford(graph):
vertices = list(graph.keys())
n = len(vertices)
src = max(vertices) + 1 # source vertex
V = [src] + vertices
graph[src] = [Adjacency(to=v, cost=0) for v in vertices]
# reverse lookup to speed up search for edges to v
rg = {}
for v in graph:
for adj in graph[v]:
rg[adj.to] = rg.get(adj.to, []) + [Adjacency(to=v, cost=adj.cost)]
dist = [{u:inf for u in V} for _ in range(n + 1)] # subproblems i to n, v of Vertex
dist[0] = {}
dist[0][src] = 0
for v in vertices:
dist[0][v] = inf
for i in range(1, n + 1):
stable = True
for v in V:
dist[i][v] = min(
dist[i - 1][v],
min(
[
dist[i - 1][adj.to] + adj.cost
for adj in rg.get(v, [])
] + [inf]
)
)
if dist[i][v] != dist[i - 1][v]:
stable = False
if stable:
print('early', i)
return [dist[i - 1][v] for v in vertices]
return None
costs = []
for edges in [g1, g2, g3]:
graph = adjacency_graph_from_edges(edges)
costs.append(bellman_ford(graph))
print(costs[-1])
None None early 28 [-7, -3, -2, -6, -4, -5, -6, -5, -5, -6, -5, -6, -3, -4, -8, -3, -12, -6, -5, -7, -8, -10, -6, -6, -12, -11, -11, -7, -5, -5, -10, -9, -10, -5, -5, -3, -5, -12, -9, -10, -11, -14, -16, -12, -13, -13, -10, -12, -9, -13, -12, -14, -13, -6, -14, -14, -12, 0, -5, -6, -5, -5, -9, -9, -4, -6, -6, -8, -5, -4, -9, -6, -2, -7, -10, -8, -5, -3, -4, -8, -8, -8, -10, -9, -8, -8, -9, -6, -8, -7, -10, -9, -13, -9, -13, -7, -6, -17, -11, -8, -12, -11, -13, -10, -15, -15, -4, -3, -5, -8, -4, -7, -6, -2, -8, -4, -6, -5, -9, -6, -7, -6, -8, -4, -10, -7, -8, -7, -9, -5, -8, -9, -9, -6, -7, -14, -9, -11, -10, -9, -11, -11, -8, -10, -7, -10, -10, -16, -12, -14, -14, -14, -11, -18, -12, -14, -6, -9, -4, -4, -5, -7, -4, -6, -6, -3, -4, -7, -4, -7, -8, -12, -6, -6, -1, -7, -10, -11, -9, -7, -6, -10, -6, -8, -8, -11, -8, -9, -7, -9, -10, -8, -14, -7, -9, -10, -15, -3, -3, -16, -13, -14, -12, -10, -15, -13, -6, -4, -7, -6, -4, -4, -5, -9, -6, -8, -2, -4, -8, -3, -7, -4, -10, -3, -9, -7, -5, -9, -4, -7, -6, -7, -7, -9, -3, -9, -10, -11, -10, -12, -12, -8, -14, -13, -13, -17, -15, -10, -10, -11, -15, -4, -6, -9, -6, -7, -11, -6, -4, -8, -6, -5, -8, -7, -4, -6, -9, -8, -8, -10, -7, -6, -9, -8, -8, -10, -4, -12, -13, -10, -10, -9, -13, -9, -10, -18, -9, -9, -13, -15, -9, -14, -14, -9, -9, -15, -11, -4, -1, -9, -6, -4, -9, 0, -6, -12, -6, -5, -12, -7, -7, -10, 0, -11, -6, -4, -8, -10, -10, -9, -10, -7, -12, -12, -10, -14, -7, -12, -12, -11, -9, -16, -7, -9, -5, -6, -5, -8, -5, -1, -1, -3, -5, -4, -4, -1, 0, -7, -4, -7, -14, -9, -9, -12, -13, -7, -11, -12, -11, -7, -9, -11, -10, -11, -14, -15, -12, -10, -8, -3, -3, -5, -6, -4, -8, -6, -8, -7, -9, -8, -12, -11, -3, -9, -10, -8, -3, -11, -9, -15, -6, -10, -10, -8, -7, -9, -9, -9, -10, -11, -13, -13, -14, -8, -8, -17, -3, -10, -4, -4, -7, -2, -6, -7, -7, -9, -1, -6, -11, -4, -9, -6, -3, -9, -5, -10, -11, -14, -9, -11, -9, -15, -16, -8, -12, -10, -14, -15, -11, -12, -11, -9, -7, -9, -7, -12, -5, -4, -8, -3, -7, -7, -8, -8, -6, -9, -7, -7, -8, -8, -10, -6, -16, -13, -7, -10, -6, -1, -3, -8, -1, -4, -7, -7, -6, -7, -9, -4, -9, -11, -10, -10, -11, -11, -9, -8, -8, -15, -9, -11, -16, -11, -1, -2, -7, -4, -6, -4, -6, -9, -3, -2, -3, -7, -7, -9, -7, -8, -6, -14, -13, -19, -12, -3, -2, -1, -2, -9, -5, -7, -7, -5, -11, -8, -10, -8, -12, -10, -11, -14, -9, -13, -4, -13, -15, -7, -6, -6, -6, -10, -4, -7, -11, -7, -8, -7, -7, -8, -15, -11, -10, -9, -12, -5, -5, -7, -5, -3, -7, -8, -9, -8, -11, -6, -2, -13, -11, -11, -9, -10, -8, -15, -5, -10, -15, -7, -8, -15, -12, -14, -12, -1, -5, -5, -5, -3, -1, -1, -7, -4, -7, -10, -5, -8, -13, -6, -8, -4, -9, -12, -13, -7, -14, -7, -3, -9, -9, -2, -11, -10, -10, -9, -8, -9, -15, -12, -11, -8, -10, -16, -5, -3, -8, -7, -7, 0, -6, -10, -11, -12, -12, -9, -9, -5, -10, -4, -4, -9, -6, -6, -5, -9, -7, -11, -12, -9, -9, -15, -12, -15, -9, -7, -4, -8, -9, -3, -5, -7, -6, -7, -7, -10, -7, -11, -13, -12, -11, -16, -4, -9, -4, -5, -7, -4, -5, -5, -5, -9, -12, -9, -6, -12, -14, -13, -4, -5, -5, -3, -8, -4, -7, -6, -5, -4, -9, -8, -3, -16, -10, -13, -13, -16, -3, -1, -4, -2, -4, -2, -7, -6, -11, -7, -14, -8, -10, -8, -5, -15, -14, -10, -16, -6, -5, -5, -7, -6, -8, -13, -6, -6, -4, -8, -8, -12, -7, -17, -13, -11, -4, -7, -6, -6, -4, -5, -1, -2, -13, -11, -12, -10, -10, -12, -6, -6, -5, -8, -7, -8, -8, -6, -7, -9, -10, -13, -17, -13, -7, -9, -9, -3, -7, -11, -11, -10, -10, -14, -7, -13, -9, -8, -6, -7, -8, -10, -5, -8, -13, -8, -16, -10, -13, -11, -6, -5, -6, -12, -14, -8, -17, -15, -3, -6, -9, -8, -14, -7, -3, -12, -8, -6, -11, -10, -13, -9, -11, -12, -12, -12, -11, -9, -8, -13, -15, -7, -8, -3, -9, -9, -14, -10, -3, -12, -12, -6, -1, -7, -11, -6, -11, -11, -9, -10, -7, -11, -8, -7, -6, -4, -10, -5, -14, -9, -10, -10, -12, -17, -4, -16, -12, -2, -3, -3, -10, -4, -11, -13, -7, -3, -2, -5, -8, -7, -12, -6, -4, -10, -15, -6, -6, -2, -5, -14, -18, -5, -2, -4, -12, -12, -7, -4, -6, -14, -11, -10, -4, -5, -4, -12, -11, -18, -14, -5, -5, -9, -6, -14, -14, -13, -3, -4, -7, -10, -11, -2, -6, -10, -7, -12, -9, -10, -15, 0, -7, -8, -9, -6, -8, -10, -5, -10, -6, -9, -12, -6, -11, -8, -11, -10, -10, -5, -4, -5, -7, -7, -1, -8, -6, -5, -13, -16, -3, -2, -15, -5, -13, -9, -1, -2, -5, -9, -9, -17, -12, -8, -9, -11, -13, -6, -8, -6, -4, -10, -10, -9, -14, -7, -8, -5, -12, -17, -9, -14, -9, -16, -4, -10, -9, -13, -14, -14, -7, -6, -3, -9, -5, -14, -8, -7, -2, -9]
print(min(costs[2]))
-19