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

3 views (last 30 days)

Show older comments

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

##### 0 Comments

### Answers (1)

Steven Lord
on 11 Oct 2022

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)

##### 2 Comments

Christine Tobler
on 11 Oct 2022

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!