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.

Question

Emmanuel 2016-10-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/308621-is-there-a-priority-queue-in-matlab-i-am-writing-a-djikstra-algorithm-which-is-slower-would-like-t

回答： Image Analyst 2016-10-22

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Image Analyst 2016-10-22

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/308621-is-there-a-priority-queue-in-matlab-i-am-writing-a-djikstra-algorithm-which-is-slower-would-like-t#answer_240205

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.