A test driven development method to validate bellman-ford algorithm works

3 views (last 30 days)
This is my function, and I'm pretty sure it works. But, I've been tasked to test my algorithm using some test-driven-development methods to prove my algorithm does what it says it does. However, I'm not quite sure how to do that in this case. The only thing I could imagine is to run another algorithm that traces out all possible paths from source (n) to root (r).
Any other suggestions?
function [d, allIterations, totalCost, path] = bellmanFord(n,E,r)
% The function takes a source node (n), an array of all edges in a graph, and a root node r
% and finds the shortest (least costly) path from n to r
N = r; % Number of Nodes
e = length(E); % Number of Edges
U = E(:,1); % Signal Propagating Nodes
V = E(:,2); % Signal Terminating Nodes
W = E(:,3); % Weights of Edges
d(1:N)=Inf; % distance of each node initialized to infinity
d(n)=0; % distance of source node intitalized to 0
predecessor(1:N)=0;
%% Create a set of labels for the node names
for i=1:N
labels(i) = strcat("Node ",int2str(i));
end
%% Bellman-Ford Algorithm
j=1;
allIterations = zeros(e*(N-1),r);
for k=1:N-1 % For each edge (u,v)...
for i = 1:e % with weight w in edges do
allIterations(j,:) = d;
v = V(i); % v_i in V
u = U(i); % u_i in U
w = W(i); % w_i in W
% t := variable for condition update
t = d(u)+w;
if (t < d(v)) % if t is less costly than v
d(v) = t;
predecessor(v) = u;
end
j = j+1;
end
end
%% Trace least costly path from source (n) to root (r)
current = r;
path = []; %empty list
while (current ~= 0)
path(end+1) = (current);
current = predecessor(current);
end
end

Answers (1)

Steven Lord
Steven Lord on 11 Oct 2022
Are you familiar with the testing frameworks included in MATLAB?
Can you think of test cases with which to try to break your code? Determine what the correct answer should be for those test cases then test whether or not your function behaves correctly.
I can think of at least one test case:
g1 = graph();
figure
plot(g1)
Here's another test case that may be interesting to try:
g2 = graph([1 2], [1 2]);
figure
plot(g2)
You could use the shortestpath function in MATLAB to check your implementation.
  2 Comments
Christine Tobler
Christine Tobler on 11 Oct 2022
I would advice to test this on a digraph which is not acyclic (not DAG), since a big part of the Bellman-Ford algorithm is concerned with cycles (e.g., Bellman-Ford should error out if there is a cycle for which the sum of the edge weights is negative - of course only if that cycle is reachable from the start node).

Sign in to comment.

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by