Demo entry 1487147

dijkstra_octave

Submitted by anonymous on Apr 18, 2015 at 12:40
Language: Octave. Code size: 7.8 kB.

%Dijkstra algorithm
%matrix needs to be squarred
%solve the problem of the smallest path between two vertices
%input: adjacent matrix. "init" and "end" are the path we're searching for
%output: the best price btw I and J
function result = dijkstra(adjMatrix, init_vertex, end_vertex)
[lines, row] = size(adjMatrix);
if (lines != row)
disp('The matrix is not square');
exit(1); %execution failed
endif
if (init_vertex - end_vertex = 0)
disp('No need to calculate! Starting point is ending point');
exit(0); %execution went ok but arguments are not
endif
fprintf('The number of lines is %i.\n',lines);
fprintf('The number of rows is %i.\n',row);
l(1:1, 1:row) = NaN;  %linear matrix which will contain the weights of every vertices
l(1, 1) = 0;
fridge(1:1, 1:row) = NaN; %linear matrix which will contain the name* of the chosen vertices
previous_l(1:1, 1:row) = NaN;
optimize_vertex = NaN;  % this variable will hold the result if the vertex needs to be changed
update(init_vertex, adjMatrix, l, fridge);
while (look(end_vertex, fridge))
u = find_smallest_index_connected(l,adjMatrix, fridge);
optimize_vertex = check(l,previous_l, fridge);
if ( optimize_vertex == (-1) )
copy(l, previous_l);%nothing to change, we update the "previous_l" matrix
update(u, adjMatrix, l, fridge);
else
while(check(l, previous_l, fridge) != (-1) )
change(fridge, optimize_vertex);
copy(previous_l, l);
update(optimize_vertex, adjMatrix, l, fridge);
endwhile
endif
endwhile
endfunction

% this function will look through the matrix to search the "vertex" value
% input: the value we're searching for and the linear_matrix containing all the values
% output: the function return true if "vertex" is found into "linear_matrix" otherwise it returns false
function result = look(vertex, linear_matrix)
[lines, length_of_linear_matrix] = size(linear_matrix);
if (lines != 1)
disp('matrix is not linear!');
exit(1);
endif
for i=1:length_of_linear_matrix
if (linear_matrix(1,i) == vertex)
return true;
endif
endfor
return false;
endfunction
% *name: the name is actually the index number of the vertex in the matrix

%this function will update the fridge
% input: the vertex(name*) from which we're updating the fridge, the fridge itself and the adjacent matrix
% output: the fridge is updated, nothing else change and returns the smallest value
function result = update(vertex, global_matrix, l , fridge)
[lines, row] = size(l);
if (lines != 1)
disp('weight matrix is not linear!');
exit(1);
endif
[lines, row] = size(fridge);
if (lines != 1)
disp('fridge matrix is not linear!');
exit(1);
endif
for i=1: row
if ( look(i, fridge) != true )  %we look if the value is not already in the fridge
if ( global_matrix(vertex,i) != NaN)
l(1,i) = l(1,i) + global_matrix(vertex, i);
endif
endif
endfor
endfunction

%this function returns the smallest value inside the specified linear_matrix
% input: a "linear_matrix"
% output: the smallest value inside "linear_matrix"
function result = find_smallest(linear_matrix, fridge)
[lines, row] = size(linear_matrix);
if (lines != 1)
disp('input list is not linear!');
exit(1);
endif
temp_value = NaN;
for i=1:row
if ( linear_matrix(1, row) > temp_value && look(row, fridge) != true)
temp_value = linear_matrix(1, row);
endif
endfor
return temp_value;
endfunction

%this function returns the smallest value inside the specified linear_matrix
% input: a "linear_matrix"
% output: the smallest index value inside "linear_matrix"
function result = find_smallest_index(linear_matrix, fridge)
[lines, row] = size(linear_matrix);
if (lines != 1)
disp('input list is not linear!');
exit(1);
endif
temp_value = NaN;
for i=1:row
if ( linear_matrix(1, row) > temp_value && look(row, fridge) != true)
temp_value = row;
endif
endfor
return temp_value;
endfunction

%this function returns the smallest value inside the specified linear_matrix and verify if the smallest value is connected
% input: a "linear_matrix", adjMatrix and fridge
% output: the smallest index value inside "linear_matrix" and connected to the last vertex in the fridge
function result = find_smallest_index_connected(linear_matrix, adjMatrix, fridge)
[lines, row] = size(linear_matrix);
if (lines != 1)
disp('input list is not linear!');
exit(1);
endif
vertex = get_last_elem(fridge);
temp_value = NaN;
for i=1:row
if ( adjMatrix(vertex, row) != NaN)
if ( linear_matrix(1, row) > temp_value && look(row, fridge) != true)
temp_value = row;
endif
endif
endfor
return temp_value;
endfunction

%this function copy the first_matrix into the second_matrix
function result = copy(first_matrix, second_matrix)
[lines1, row1] = size(first_matrix);
[lines2, row2] = size(second_matrix);
if ( lines1 != lines2 || row1 != row2)
disp('matrices have differents sizes');
exit(1);
endif
for i=1:lines1
for j=1:row1
second_matrix(i,j) = first_matrix(i,j);
endfor
endfor
return second_matrix;
endfunction

% this function check with the actual weight list ("l") and the previous weight list ("previous_l") if there's something to change in the fridge
% input: "l", "previous_l"
% output: returns -1 if nothing need to be changed otherwise it returns the index making trouble
function result = check( weighted_graph, previous_weighted_graph, fridge)
[lines1, row1] = size(weighted_graph);
[lines2, row2] = size(previous_weighted_graph);
if ( lines1 != lines2 || row1 != row2)
disp('weighted graphs have differents sizes');
exit(1);
endif
for i=1: row1
if ( weighted_graph(1, i) > previous_weighted_graph(1, i) )
return i;
else
return (-1); % nothing to change
endif
endfor
endfunction

% this funtion add a value to the linear matrix specified in arguments at his end
% input: linear_matrix, element
% output: element is put at the end of the list
function result = add(linear_matrix, element)
[lines, row] = size(linear_matrix);
if (lines != 1)
disp('input matrix is not linear! Its better to stop the program here ');
exit(1);
endif
if ( linear_matrix(1,row) != NaN) %we assume the fact that the list is filled one by one until the end
disp('the matrix is full!');
exit(1);
endif
for i=1:row
if (linear_matrix(1,i) == NaN)
linear_matrix(1,i) = element;
return 0;
endif
endfor
endfunction

% this funtion returns the last element != NaN
% input: linear_matrix
% output: element is put at the end of the list
function result = get_last_elem(linear_matrix)
[lines, row] = size(linear_matrix);
if (lines != 1)
disp('input matrix is not linear! Its better to stop the program here ');
exit(1);
endif
if (linear_matrix(1,1 == NaN)
disp('The linear matrix is empty!');
exit(1);
endif
if ( linear_matrix(1,row) != NaN) %we assume the fact that the list is filled one by one until the end
return linear_matrix(1, row);
endif
for i=1:row
if (linear_matrix(1,i) == NaN)
return linear_matrix(1, i-1);
endif
endfor
endfunction

%this function change the last element by another
function result= change(linear_matrix, element)
[lines, row] = size(linear_matrix);
if (lines != 1)
disp('input matrix is not linear! Its better to stop the program here ');
exit(1);
endif
if ( linear_matrix(1,row) != NaN) %we assume the fact that the list is filled one by one until the end
linear_matrix(1, row -1) = element;
linear_matrix(1, row) = NaN;
return 0;
endif
for i=1:row
if (linear_matrix(1,i) ==NaN)
linear_matrix(1, i-1) = NaN;
linear_matrix(1, i-2) = element;
return 0;
endif
endfor
return -1;
endfunction

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.