Bellman Ford Algorithm In Python

Chapter: Python Last Updated: 25-03-2023 18:01:19 UTC

Program:

            /* ............... START ............... */
                
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        # Step 1: Initialize distances from src to all other vertices
        # as INFINITE
        dist = [float("Inf")] * self.V
        dist[src] = 0

        # Step 2: Relax all edges |V| - 1 times. A simple shortest 
        # path from src to any other vertex can have at most |V| - 1 
        # edges
        for i in range(self.V - 1):
            # Update dist value and parent index of the adjacent vertices
            # of the picked vertex. Consider only those vertices which are
            # still in queue
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        # Step 3: Check for negative-weight cycles. The above step 
        # guarantees shortest distances if graph doesn't contain 
        # negative weight cycle. If we get a shorter path, then there
        # is a cycle
        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        # print all distance
        for i in range(self.V):
            print("Vertex distance from source", i, "is:", dist[i])

# Example usage:
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)

                /* ............... END ............... */
        

Output

Vertex distance from source 0 is: 0
Vertex distance from source 1 is: -1
Vertex distance from source 2 is: 2
Vertex distance from source 3 is: -2
Vertex distance from source 4 is: 1
This output indicates the shortest distances from the source node 0 to all other nodes in the graph. 
For example, the shortest distance from node 0 to node 2 is 2, and the shortest distance from 
node 0 to node 3 is -2. Note that the algorithm correctly identifies that the graph does not 
contain a negative-weight cycle.

Notes:

  • The Bellman-Ford algorithm is a well-known algorithm for finding the shortest path between nodes in a weighted graph. The algorithm works by iteratively relaxing the edges of the graph, reducing the distance estimate for each node until the shortest path is found. The algorithm also detects negative-weight cycles, which can cause problems for other shortest path algorithms.
  • In this Python implementation, the Graph class represents the weighted graph. The class constructor takes the number of vertices in the graph as an argument, and the add_edge method is used to add edges to the graph. The bellman_ford method takes the source node as an argument and uses the Bellman-Ford algorithm to calculate the shortest distances from the source node to all other nodes in the graph.
  • The bellman_ford method first initializes an array of distances dist to all nodes as infinite, except for the source node, which is initialized to 0. It then relaxes each edge of the graph V-1 times, where V is the number of vertices in the graph. During each relaxation, the method updates the distance estimate for each node based on the distances of its neighbors. If the updated distance is smaller than the current estimate, the estimate is updated.
  • After V-1 rounds of relaxation, the method checks for negative-weight cycles by attempting to relax each edge once more. If any distance estimate can be updated after this final relaxation step, then the graph contains a negative-weight cycle.
  • Finally, the method prints the shortest distances from the source node to all other nodes in the graph. If a negative-weight cycle was detected, the method prints a message indicating this.

Tags

#Bellman Ford Algorithm In Python #Bellman Ford algorithm code #Bellman-Ford algorithm example step by step

Similar Programs Chapter Last Updated
Python Program To Replace Characters In A String Python 03-06-2023
Python Program To Replace Blank Space With Hyphen Python 30-05-2023
Python Regex Match End Of String Python 30-05-2023
Python Check If String Contains Certain Characters Python 30-05-2023
How To Get The Length Of An Array In Python Python 27-05-2023
How To Find The First Duplicate Element In A Given Array Of Integers In Python Python 27-05-2023
How To Get Key And Value From Dictionary In Python Python 24-05-2023
Merge Two Dictionaries In Python Python 24-05-2023
Convert Two Lists Into A Dictionary In Python Python 24-05-2023
How To Remove An Element From A Set In Python Python 19-05-2023
Return A New Set Of Identical Items From Two Sets In Python Python 19-05-2023
Add A List Of Elements To A Set In Python Python 19-05-2023
Check If Two Lists Have At-least One Element Common In Python Python 17-05-2023
Python Program To Remove All The Occurrences Of An Element From A List Python 17-05-2023
Write A Python Program To Turn Every Item Of A List Into Its Square Python 15-05-2023
Write A Python Program To Concatenate Two Lists Index-wise Python 15-05-2023
Write A Python Program To Reverse A List Python 15-05-2023
How To Run Python Program In Terminal Python 14-05-2023
Python Date Format AM PM Python 14-05-2023
Python Add Months To Date Example Python 14-05-2023
Python Add Days To Date Example Python 14-05-2023
Python List All Elements In List Python 30-04-2023
Python Program To Check Prime Number Using Function Python 27-04-2023
Python Program To Sum All The Items In A List Python 27-04-2023
Python Interest Calculator Python 27-04-2023
Python Program To Print Calendar Of Any Year Python 26-04-2023
Python Program To Print Calendar Python 26-04-2023
How To Create XML File In Python Python 23-04-2023
Python Run Function At Specific Time Everyday Python 22-04-2023
Python Program For String Reverse Python 20-04-2023

1 2 3