W3Schools Tryit Editor

Python

Java

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            #self.adj_matrix[v][u] = weight  # For undirected graph

def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

def bellman_ford(self, start_vertex_data):
        start_vertex = self.vertex_data.index(start_vertex_data)
        distances = [float('inf')] * self.size
        distances[start_vertex] = 0

for i in range(self.size - 1):
            for u in range(self.size):
                for v in range(self.size):
                    if self.adj_matrix[u][v] != 0:
                        if distances[u] + self.adj_matrix[u][v] < distances[v]:
                            distances[v] = distances[u] + self.adj_matrix[u][v]
                            print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")

# Negative cycle detection
        for u in range(self.size):
            for v in range(self.size):
                if self.adj_matrix[u][v] != 0:
                    if distances[u] + self.adj_matrix[u][v] < distances[v]:
                        return (True, None)  # Indicate a negative cycle was found

return (False, distances)  # Indicate no negative cycle and return distances

g = Graph(5)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')

g.add_edge(3, 0, 4)  # D -> A, weight 4
g.add_edge(3, 2, 7)  # D -> C, weight 7
g.add_edge(3, 4, 3)  # D -> E, weight 3
g.add_edge(0, 2, 4)  # A -> C, weight 4
g.add_edge(2, 0, -9) # C -> A, weight -9
g.add_edge(0, 4, 5)  # A -> E, weight 5
g.add_edge(4, 2, 3)  # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2)  # E -> B, weight 2

# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
negative_cycle, distances = g.bellman_ford('D')
if not negative_cycle:
    for i, d in enumerate(distances):
        print(f"Distance from D to {g.vertex_data[i]}: {d}")
else:
    print("Negative weight cycle detected. Cannot compute shortest paths.")
    
#Python

​x
 
class Graph:    def __init__(self, size):        self.adj_matrix = [[0] * size for _ in range(size)]        self.size = size        self.vertex_data = [''] * size​    def add_edge(self, u, v, weight):        if 0 <= u < self.size and 0 <= v < self.size:            self.adj_matrix[u][v] = weight            #self.adj_matrix[v][u] = weight  # For undirected graph​    def add_vertex_data(self, vertex, data):        if 0 <= vertex < self.size:            self.vertex_data[vertex] = data​    def bellman_ford(self, start_vertex_data):        start_vertex = self.vertex_data.index(start_vertex_data)        distances = [float('inf')] * self.size        distances[start_vertex] = 0​        for i in range(self.size - 1):            for u in range(self.size):                for v in range(self.size):                    if self.adj_matrix[u][v] != 0:                        if distances[u] + self.adj_matrix[u][v] < distances[v]:                            distances[v] = distances[u] + self.adj_matrix[u][v]                            print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")​        # Negative cycle detection        for u in range(self.size):            for v in range(self.size):                if self.adj_matrix[u][v] != 0:                    if distances[u] + self.adj_matrix[u][v] < distances[v]:                        return (True, None)  # Indicate a negative cycle was found​        return (False, distances)  # Indicate no negative cycle and return distances​g = Graph(5)​g.add_vertex_data(0, 'A')g.add_vertex_data(1, 'B')