Bellman ford algorithm time complexity
Considering the below graph for describing the time complexity of the Bellman-Ford algorithm.
Variables description:
'n' indicates the array length of all nodes
'm' indicates the array length of all edges
Two loops will be run for finding out and compare the distance value between nodes. The codes will clear the fact,
for ( int i =1; i<n; i++)
{
for (int j=1; j<m; j++)
{
if (dist[e][v] > dist[e][u])
{
}
}
}
The two loops will run for n-th time and m-time. So, the complexity will be,
Time complexity = O (time run for n nodes) * O (time run for m nodes)
= O (n) * O (m)
= O (n*m)
= O (nm)
So, the time complexity of the bellman ford algorithm is O(nm)
Optimization: Reduce the time complexity of Bellman-Ford Algorithm
1. In the n loop ( the first loop), if the m edge value has no update then we can break the n loop at this time.
2. Before running the Bellman-Ford algorithm, the edges can be randomly picked up for processing.
Read Similar Post: