Borrar filtros
Borrar filtros

Is there a priority queue in matlab? I am writing a Djikstra algorithm which is slower. Would like to use a queue to make the code run faster.

4 visualizaciones (últimos 30 días)
I am trying to write a Djikstra's algorithm. But it takes for ever to run for 1000x1000 matrix. I was wondering if there were any ways I could use a priority queue to sort my open list and make my code run faster.
function hMap = djikstra(B,R)
%B = Cost Map
%R = Initial Position of the Robot
fprintf('In Dijkstra');
hMap = Inf(length(B)); % Assigning infinity
hMap(R(1),R(2)) = 0 ; % source node
open = [];
open = [R(1),R(2),0];
closed = [];
closed = [closed; open(1,1:2)]; %Put current source node in closed
x = R(1);
y = R(2);
while(size(open) ~= 0)
if(x-1 ~=0)
if(sum(ismember(closed(:,1:2),[x-1,y],'rows'))== 0)
cost = hMap(x,y)+ B(x-1,y);
hMap(x-1,y) = min(cost,hMap(x-1,y));
open = [open;x-1,y,hMap(x-1,y)];
end
end
if(x+1 <= length(B))
if(sum(ismember(closed(:,1:2),[x+1,y],'rows'))== 0)
cost = hMap(x,y)+ B(x+1,y) ;
hMap(x+1,y) = min(cost,hMap(x+1,y));
open = [open;x+1,y,hMap(x+1,y)];
end
end
if(y-1 ~= 0)
if(sum(ismember(closed(:,1:2),[x,y-1],'rows'))== 0)
cost = hMap(x,y)+ B(x,y-1);
hMap(x,y-1) = min(cost, hMap(x,y-1));
open = [open;x,y-1,hMap(x,y-1)] ;
end
end
if(y+1 <= length(B))
if(sum(ismember(closed(:,1:2),[x,y+1],'rows'))== 0)
cost = hMap(x,y)+ B(x,y+1);
hMap(x,y+1) = min(cost,hMap(x,y+1));
open = [open;x,y+1,hMap(x,y+1)];
end
end
closed = [closed;x,y];
open = open(2:size(open,1),:); %Removing source element from the open list
open = unique(open,'rows');
open = sortrows(open,3); % Sorting w.r.t G Value
if(size(open) ~= 0)
x = open(1,1)
y = open(1,2)
end
end
end

Respuestas (1)

Image Analyst
Image Analyst el 22 de Oct. de 2016
It would be shorter if you used the built in shortestpath() function
path = shortestpath(G,s,t) computes the shortest path starting at source node s and ending at target node t. If the graph is weighted (that is, G.Edges contains a variable Weight), then those weights are used as the distances along the edges in the graph. Otherwise, all edge distances are taken to be 1.

Categorías

Más información sobre Problem-Based Optimization Setup 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!

Translated by