Click here to Skip to main content
15,791,934 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
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')]]


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:

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

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