Bellman–Ford Algorithm

  Bellman–Ford Algorithm.

When we are dealing with a Graph that has negative weights, Dijkstra's algorithm does not work.

In this case, we need to use another algorithm called the "Bellman-Ford" algorithm.

The Bellman-Ford algorithm computes the shortest distances from a root vertex to all vertices like Dijkstra.

It is a simpler algorithm than Dijkstra; however, the time complexity is O(VE) which is higher than Dijkstra. 

For Bellman-Ford,  it takes a (number of connections - 1) iterations to find the smallest cost from the root to all vertices.

It iteratively reduces the weight of the connections as new paths are explored. 

Here is the step for implementing the Bellman-Ford algorithm.

1. Set all the possible vertices to infinity.
2. Set the cost of the current node to the current node as 0.
3. For all edges or connections, If cost(currentNode) + weight(currentNode, targetNode) < cost(currentNode): cost(targetNode) = cost(currentNode) + weight(currentNode, targetNode)
4. Repeat the 3 for the number of (vertices -1)
5. If you want to find whether the graph has a negative loop, execute 3. 
6. If cost(currentNode) + weight(currentNode, targetNode) < cost(currentNode) is true for any node in the graph, then the graph has at least one negative loop.

##############################################################

bool BellmanFord(int iWantedNode) {

iResultSaveArray[1] = 0;

for (int loop = 1; loop <= iNodeNum; loop++) {

for (int i = 1; i <= iNodeNum; i++) {

for (int j = 0; j < iStoreConnectionArray[i].size(); j++) {

int iCurrentNode = i;

int iNextNode = iStoreConnectionArray[iCurrentNode][j].first;

int iNextWeight = iStoreConnectionArray[iCurrentNode][j].second;

if (iResultSaveArray[iCurrentNode] == INF)continue;

if (iResultSaveArray[iNextNode] > iNextWeight + iResultSaveArray[iCurrentNode]) {

iResultSaveArray[iNextNode] = iNextWeight + iResultSaveArray[iCurrentNode];

if (loop == iNodeNum) {

cout << -1 << endl;

return true;

}

}

}

}

}

for (int i = 2; i <= iNodeNum; i++) {

if (iResultSaveArray[i] != INF) {

cout << iResultSaveArray[i] << endl;

}

else {

cout << -1 << endl;

}

}

return false;

}

##############################################################

References:

https://www.javatpoint.com/bellman-ford-algorithm

https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/

https://www.educative.io/answers/what-is-the-bellman-ford-algorithm