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
    add(fridge, init_vertex);
    update(init_vertex, adjMatrix, l, fridge);
    while (look(end_vertex, fridge))
 	u = find_smallest_index_connected(l,adjMatrix, fridge);
 	add(fridge, u);
 	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.

Delete this entry (admin only).