15,791,934 members

See more:

Python

def hasNegativeCycle(weight_matrix): n = len(weight_matrix) has_negative_cycle = False #missing code return has_negative_cycle weight_matrix = [[float('inf'), 5, 2], [5, float('inf'), -10], [2, -10, float('inf')]] print(hasNegativeCycle())

How do I...Given an adjacency matrix with weights of edges instead of 0 and 1 (if there is no edge between the vertices that value is replaced with float("inf")), return True if there is a cycle with negative cost in the graph and False if there is no such cycle.

Python

if cost[v][k] != float('inf') and cost[k][u] != float('inf') \ and (cost[v][k] + cost[k][u] < cost[v][u]): cost[v][u] = cost[v][k] + cost[k][u] path[v][u] = path[k][u]

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900