-
Notifications
You must be signed in to change notification settings - Fork 2
/
dijkstraR.m
95 lines (95 loc) · 3.36 KB
/
dijkstraR.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
%dijkstra得到所有最短路径
function [L,sp, spcost] =dijkstraR(W, s, d,q)
% W 邻接矩阵 % s 起点 % d 终点 %l 约束路径条数
% L 约束路径条数 % sp 所有路径矩阵 %spcost 最短路径距离
L = q;
n=size(W,1);
S(1:n) = 0; %s, vector, set of visited vectors
dist(1:n) = inf; % it stores the shortest distance between the source node and any other node;
prev = cell(1,n);
% prev(1:n) = n+1; % Previous node, informs about the best previous node known to reach each network node
prev(1:n) = {
n+1};
dist(s) = 0;
counter(1:n) = 1;
while sum(S)~=n
candidate=[];
for i=1:n
if S(i)==0
candidate=[candidate dist(i)];
else
candidate=[candidate inf];
end
end
[u_index,u]=min(candidate);
S(u)=1;
for i=1:n
if(dist(u)+W(u,i))<dist(i) % SEE DOCUMENTATION Switch 1 (add)
%if (1 - (1 - dist(u)) * (1 - W(u,i))) < dist(i) % SEE DOCUMENTATION Switch 1 (mult)
% dist(i) = (1 - (1 - dist(u)) * (1 - W(u,i))); % SEE DOCUMENTATION Switch 2 (mult)
dist(i)=dist(u)+W(u,i); % SEE DOCUMENTATION switch 2 (add)
prev(1,i) = {
u};
if counter > 1
for j=2:counter
prev(counter,i) = {
NaN};
end
end
counter(i) = 1;
elseif(dist(u)+W(u,i)) == dist(i) % SEE DOCUMENTATION Switch 3 (add)
%elseif(1 - (1 - dist(u)) * (1 - W(u,i))) == dist(i) % SEE DOCUMENTATION Switch 3 (mult)
prev(counter(i)+1,i) = {
u};
counter(i) = counter(i)+1;
end
end
end
% Define a vector to represent how many ties are contained in the prev cell
% array corresponding to each node
prevcolindex = ones(1,n);
for i = 1:n
for j = 2:size(prev,1)
if isempty(prev{j,i}) == 1
break;
else
prevcolindex(i) = j;
end
end
end
% Trace the branches of the path backwards beginning at d using the prev cell array. Record
% the history of all steps each branch of the shortest path in backpaths cell array.
% (Each step backwards along any branch in the path trace occupies a new cell in backpaths.)
backpaths = cell(1,1);
backpaths(1,1) = {
d};
counters = 1;
counterf = 1;
test = 0;
while all(test == s) == 0 % The stopping criteria is that all remaining active branches (ie step histories that have not yet arrived at s) arrive at s simultaneuously
test = s;
for j = counters:counterf
if backpaths{j}(1) == s
continue; % If a step history his already arrived at s, it is skipped
end
counterm = length(backpaths);
for i = 1:prevcolindex(backpaths{j}) % Step backwards along each branch of the shortest path, and record the resulting history in a new cell in backpaths
backpaths{counterm+i} = cat(2,prev{i,backpaths{j}(1)},backpaths{j});
end
test = cat(1,test,prev{i,backpaths{j}(1)});
end
counters = 1+counterf;
counterf = length(backpaths);
end
% Extract the step histories that end (ie begin) at node s, and save them
% to sp (the shortest path array)
sp = cell(1,1);
for i = 1:counterf
if backpaths{i}(1) == s && isempty(sp{1}) == 1
sp = backpaths(i);
elseif backpaths{i}(1) == s && isempty(sp{1}) == 0
sp = cat(1,sp,backpaths(i));
end
end
spcost = dist(d);
end