-
Notifications
You must be signed in to change notification settings - Fork 29
/
dijkstra.m
70 lines (62 loc) · 2.39 KB
/
dijkstra.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
function [shortestPath, totalCost] = dijkstra(netCostMatrix, s, d)
%==============================================================
% shortestPath: the list of nodes in the shortestPath from source to destination;
% totalCost: the total cost of the shortestPath;
% farthestNode: the farthest node to reach for each node after performing the routing;
% n: the number of nodes in the network;
% s: source node index;
% d: destination node index;
%==============================================================
% Code by:
% ++by Xiaodong Wang
% ++23 Jul 2004 (Updated 29 Jul 2004)
% ++http://www.mathworks.com/matlabcentral/fileexchange/5550-dijkstra-shortest-path-routing
% Modifications (simplifications) by Meral Shirazipour 9 Dec 2009
%==============================================================
n = size(netCostMatrix,1);
for i = 1:n
% initialize the farthest node to be itself;
farthestPrevHop(i) = i; % used to compute the RTS/CTS range;
farthestNextHop(i) = i;
end
% all the nodes are un-visited;
visited(1:n) = false;
distance(1:n) = inf; % it stores the shortest distance between each node and the source node;
parent(1:n) = 0;
distance(s) = 0;
for i = 1:(n-1),
temp = [];
for h = 1:n,
if ~visited(h) % in the tree;
temp=[temp distance(h)];
else
temp=[temp inf];
end
end;
[t, u] = min(temp); % it starts from node with the shortest distance to the source;
visited(u) = true; % mark it as visited;
for v = 1:n, % for each neighbors of node u;
if ( ( netCostMatrix(u, v) + distance(u)) < distance(v) )
distance(v) = distance(u) + netCostMatrix(u, v); % update the shortest distance when a shorter shortestPath is found;
parent(v) = u; % update its parent;
end;
end;
end;
shortestPath = [];
if parent(d) ~= 0 % if there is a shortestPath!
t = d;
shortestPath = [d];
while t ~= s
p = parent(t);
shortestPath = [p shortestPath];
if netCostMatrix(t, farthestPrevHop(t)) < netCostMatrix(t, p)
farthestPrevHop(t) = p;
end;
if netCostMatrix(p, farthestNextHop(p)) < netCostMatrix(p, t)
farthestNextHop(p) = t;
end;
t = p;
end;
end;
totalCost = distance(d);
%return;