BELLMAN-FORD

Searching the shortest path

Algorithm Bellman Ford Project Implementation

ALGORITHM

The Bellman-Ford optimization algorithm is used to find the shortest paths between all nodes in a directed or undirected weighted graph from a source node. This algorithm can handle edges with negative weights, which makes it useful in some situations. Furthermore, it finds the shortest distances using an edge relaxation strategy repeatedly. It starts by assigning all nodes an infinite distance, except the source node, which has a distance of 0. Then, iterates through the next two V1 steps, where V is the total number of nodes in the graph


  • Edge relaxation phase: For each edge (u, v) in the graph, try to increase the distance to node v from node u by adding the weight of the edge to the current distance of u and comparing the result with the current distance of v. The distance of v is updated if it is shorter.

  • Negative Cycle Detection Phase: After the V-1 edge relaxation phases, an additional phase is performed to determine if there is a negative cycle in the graph. If an improvement is found in any of the distances, a negative cycle can be reached from the source.


The algorithm will calculate the shortest distance between the source and all other nodes when the V-1 edge relaxation phases have finished. If there are no negative cycles, these distances are the shortest possible. A negative cycle indicates that there is no optimal solution, since the distance can continue to increase without end.

RICHARD BELLMAN

SeñorBellman

Richard Bellman (1920-1984) was an American applied mathematician and computer scientist. He is best known for his pioneering work in the field of dynamic programming, which has had a profound impact on various disciplines, including mathematics, operations research, and computer science. Bellman developed the Bellman equation, a fundamental equation in optimization theory, and his research laid the foundation for the efficient solution of complex problems in control theory and stochastic optimization. His contributions to the field earned him numerous accolades, including the IEEE Medal of Honor in 1979.

LESTER FORD

SeñorFord

Lester Randolph Ford Sr. (1886-1967) was an American mathematician known for his significant contributions to number theory and mathematical research. He served as the president of the Mathematical Association of America (MAA) from 1945 to 1946. Ford's notable achievements include his work on continued fractions, Diophantine approximation, and the theory of numbers. He made important discoveries in the distribution of prime numbers and continued fractions, and his research has had a lasting impact on the field of mathematics.

ABOUT PROJECT

For the Computer Networks course, a report will be made where a deep investigation on the Bellman Ford algorithm will be carried out and the relevant information will be documented, which has been collected from various secure sources such as articles, scientific journals, etc. All this, in order to be able to optimize the code when implementing the algorithm, so that it has a better efficiency in terms of time, resources used and with less memory consumption without altering the functionality. The results that will be obtained through experimentation are recorded in the report since they have subsequently been analyzed and interpreted for the conclusions of the case.

IMPLEMENTATION