Bellman Ford Algorithm
Updated 23 May 2017
The above code is used to find the minimum distance between the Source node (A) to all the given nodes, via the Bellman Ford Algorithm where the matrix m is composed of the source nodes, matrix n consists of the destination nodes, and w reperesnts the corresponding weights of the edges connecting the source and destination. ‘N’ represents the number of nodes, and e_num represents the number of edges in the network.
The basic syntaxes which are used are as follows:
1. S= Sparse(m,n,w): It generates a sparse matrix from triplets m, n and w such that S(m(k),n(k))=w(k). Here, the matrix m represents the list of source nodes in the network, and the matrix represents the destination nodes, and matrix w represents the corresponding edge weights.
2. G=digraph(m,n,w,): Creates a directed graph G of all the source nodes in m to all destination nodes n, and it also specifies the edge weights from the array of weights w.
3. Initialize the shortest distance of the source node to be 0, and shortest distance of all the remaining nodes to infinity, as done in the lines 11 and 12 using the variable v_weight(). All distances are to be evaluated from source node. The source node is designated by s.
4. We also initialize the parent node of every node in the network to zero, as done by the variable predecessor().
5. The basic concept to be used in the algorithm is that every edge is traversed (v_num-1) times, so we take a loop and evaluate the correct value of the v_weights of all the nodes from the starting node by using the theory of relaxation concept explained earlier.
6. After we have calculated the distance of all nodes from the source node, by incorporating the theory of relaxation, we now consider a matrix M which gives us the indices of the shortest path (it specifies the nodes) from the source node to a desired destination node as specified by the user. TotalCost is a variable which is used to store the value of the total distance of the source node to the specified destination node.
7. TR=Shortestpath(G,s,d): Calculates the shortest path from source node s to specified destination node d in the directed graph G.
8. highlight(p, TR, ‘EdgeColor’,’g’): highlights a subset of nodes included in the shortest path TR by changing their color to green.
Anwaya rath (2023). Bellman Ford Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/63069-bellman-ford-algorithm), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform CompatibilityWindows macOS Linux
- MATLAB > Mathematics > Graph and Network Algorithms > Construction >
- MATLAB > Mathematics > Graph and Network Algorithms > Construction > Directed Graphs >
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!
Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.