A test driven development method to validate bellman-ford algorithm works
3 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Respuestas (1)
Steven Lord
el 11 de Oct. de 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 comentarios
Christine Tobler
el 11 de Oct. de 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).
Ver también
Categorías
Más información sobre Hypothesis Tests en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!