-
Notifications
You must be signed in to change notification settings - Fork 1
/
ShortestPathSym.m
67 lines (64 loc) · 2.02 KB
/
ShortestPathSym.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
function [route]= ShortestPathSym(custos,origem,destino)
R= [0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0];
[n n1]=size(custos);
if n~=17 || n1~=17
route=[-1];
elseif origem == destino || origem>17 || origem<1 || destino>17 || destino<1
route=[-2];
elseif min(min(custos))<0
route=[-3];
else
custos= custos + custos.';
S=zeros(1,n);
S(origem)= 1;
p=zeros(1,n);
maximo= max(max(custos))*n+1;
c=maximo*ones(1,n);
c(origem)= 0;
aux= origem;
while S(destino) == 0
for i = 1:17
if R(aux,i)>0 && c(i)>(c(aux)+custos(aux,i))
c(i)= c(aux)+custos(aux,i);
p(i)= aux;
end
end
aux= 0;
cost= maximo;
for i = 1:17
if S(i)==0 && c(i)<cost
aux= i;
cost= c(i);
end
end
if c(destino)==cost
aux= destino;
end
S(aux)= 1;
end
route= [destino];
aux= destino;
while p(aux)~=origem
route= [p(aux) route];
aux= p(aux);
end
route= [origem route];
route(17)= 0;
end
end