Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@jcchurch
Created April 20, 2011 03:22
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save jcchurch/930280 to your computer and use it in GitHub Desktop.
Save jcchurch/930280 to your computer and use it in GitHub Desktop.
Dijkstra's Algorithm in Matlab
function D = dijkstra(G, pairs)
% This function takes an adjacency matrix called G
% and a p-by-2 matrix called pairs.
% The pairs matrix will contain pairs of indices.
% This function will determine the shortest distance from
% the first index in the pair to the second index for
% every pair in matrix pairs.
%
% The function will only return a p-by-1 matrix of shortest
% distances. I could use it to also return the shortest path,
% but I don't need that data, so only shortest distance is
% calculated.
p = size(pairs, 1); % Number of pairs
v = size(G, 1); % Number of vertices
D = [];
for i = 1:v
for j = 1:v
if G(i,j) <= esp
G(i,j) = inf
end
end
end
for i = 1:p
dist = inf(1, v);
seen = ones(1, v);
not_seen = v;
dist(1, pairs(i,1)) = 0;
while not_seen > 0
[distance index] = min(dist .* seen);
if distance == inf
break;
end
if index == pairs(i,2)
break;
end
seen(index) = inf;
not_seen = not_seen - 1;
for n = 1:v
if seen(n) == 1
alt = distance + G(index, n);
if alt < dist(n)
dist(n) = alt;
end
end
end
end
D = [D ; dist(pairs(i,2))];
end
end
@anaswara
Copy link

can u pls mention what is esp here?

@shima1
Copy link

shima1 commented Dec 16, 2013

can you tell me what do mean esp and how i should give G?
plz give some example.

@regularNN
Copy link

that is not "esp" but 'eps' .

@hkarachalios
Copy link

how could we use this code to return the shortest path as well?

@rizkirama
Copy link

Sir, how do I use this syntax, why when I run it doesn't work ??
does it affect the matlab application that is used

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment