Click here to Skip to main content
15,175,525 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
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.

What I have tried:

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]
Posted
Updated 11-Mar-21 16:05pm
v3

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