Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Network Attack by Moff
from collections import defaultdict
class EdgeWeightedDigraph(object):
def __init__(self):
self.adjacent = defaultdict(dict)
self.vertices_count = 0
def add_edge(self, v1, v2, weight):
self.adjacent[v1][v2] = weight
def load(self, matrix):
for row in range(len(matrix)):
for col in range(len(matrix)):
if row != col and matrix[row][col] == 1:
self.add_edge(row, col, matrix[col][col])
self.vertices_count = len(matrix)
@property
def vertices(self):
return range(self.vertices_count)
class BellmanFordSP(object):
def __init__(self, graph, v0):
self.dist_to = {v: float('inf') for v in graph.vertices}
self.dist_to[v0] = 0
for _ in range(graph.vertices_count):
for v1 in graph.vertices:
for v2, w in graph.adjacent[v1].items():
self.relax(v1, v2, w)
def relax(self, v1, v2, w):
if self.dist_to[v2] > self.dist_to[v1] + w:
self.dist_to[v2] = self.dist_to[v1] + w
def capture(m):
g = EdgeWeightedDigraph()
g.load(m)
return max(BellmanFordSP(g, 0).dist_to.values())
Aug. 3, 2015
