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

5 visualizzazioni (ultimi 30 giorni)
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

Risposte (1)

Steven Lord
Steven Lord il 11 Ott 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 Commenti
Fouad Azar
Fouad Azar il 11 Ott 2022
I have created a digraph G=digraph(A), where A is a random DAG adjacency matrix.
I also created an interactive script where you can enter the number of nodes you and a slider that adjusts the source node.
Finally, I use the shortestPathTree property of G to validate that my path function is correct.
Would these methods be considered as "test-driven development"?
Christine Tobler
Christine Tobler il 11 Ott 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).

Accedi per commentare.

Community Treasure Hunt

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

Start Hunting!

Translated by