dijkstra算法matlab代码

Dijkstra算法是一种用于求单源最短路径的算法。下面是一个简单的matlab代码实现例子：

function [dist,path,pred] = dijkstra(adj,src)
% DIJKSTRA shortest path from src to all other nodes
%
% [dist,path,pred] = dijkstra(adj,src)
%
%    adj : NxN sparse adjacency matrix
%    src : starting node
%
%  dist : shortest path distance from src to all other nodes
%  path : shortest path from src to all other nodes
%  pred : predecessor node in shortest path
%

n = size(adj,1);

dist = inf(1,n);
pred = zeros(1,n);
path = inf(n,n);
visited = false(1,n);

dist(src) = 0;

for k = 1:(n-1)
   [d,u] = min(dist(~visited));
   visited(u) = true;
   for v = find(adj(u,:))
      if dist(v) > dist(u) + adj(u,v)
         dist(v) = dist(u) + adj(u,v);
         pred(v) = u;
      end
   end
end

for v = find(dist<inf)
   path(src,v) = v;
   k = pred(v);
   while k ~= src
      path(src,v) = [k path(src,v)];
      k = pred(k);
   end
end

上面的代码是用邻接矩阵存储图，如果是邻接表存储，可以换成相应的读取方式。