LP_and_Heuristics_examples/Shortest-Path_DIJKSTRA_Ex2.mos at main · AACsempre/LP_and_Heuristics_examples · GitHub

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
96
97
98
99
100
101
102
103
104
model SPP_Dijkstra
!Caminhos ótimos em redes - ALGORITMO DE DIJKSTRA
uses "mmive"

declarations

	Nodes = 11
	!sets
	N = 1..Nodes
	!data
	c: array (N,N) of real !Cost vector
	A: dynamic array (N,N) of real ! Auxiliar vector
	d: array(N) of real
	L: array(N) of real
	Fix:real

end-declarations

!---------------------------------------------
! Model Data
No:=0

	!	1	2	3	4	5	6	7	8	9	10	11
c:: [	0,	1,	No,	No,	10,	No,	No,	9,	No,	No,	No, 	!1
		1,	0,	1,	No,	5,	No,	No,	No,	No,	No,	No,		!2
		No,	No,	0,	10,	2,	6,	No,	No,	No,	No,	No,		!3
		No,	No,	No,	0,	No,	4,	7,	No,	No,	No,	5,		!4
		No,	5,	No,	No,	0,	2,	No,	1,	4,	No,	No,		!5
		No,	No,	No,	4,	No,	0,	9,	No,	1,	10,	No,		!6
		No,	No,	No,	No,	No,	No,	0,	No,	No,	1,	2,		!7
		9,	No,	No,	No,	1,	No,	No,	0,	2,	No,	No,		!8
		No,	No,	No,	No,	No,	No,	No,	No,	0,	1,	No,		!9
		No,	No,	No,	No,	No,	10,	1,	No,	No,	0,	No,		!10
		No,	No,	No,	No,	No,	No,	No,	No,	No,	No,	0]		!11

forall(i,j in N|c(i,j)<>No)
	A(i,j):=1

!************************* ALGORITMO DE DIJKSTRA *************************

Infinite:=10000

forall (s in N) do  		!pode não ser possível...

!Initialization
d(s):=0
L(s):=0
forall(j in N|j<>s) do
	d(j):=Infinite
	L(j):=1
end-do
i:=s

repeat
	Stop:=1

!Update
	forall(j in N|A(i,j)=1 and L(j)=1)
		if d(j)>d(i)+c(i,j) then
			d(j):=d(i)+c(i,j)
			p(j):=i
		end-if

!Closure
	Stop2:=0
	Fix:=Infinite
	forall(j in N|L(j)=1)
		if d(j)<Fix then
			Fix:=d(j)
			i:=j
			Stop2:=1
		end-if
	L(i):=0

!Termination
	forall(j in N)
		if L(j)=1 then
			Stop:=0
			k:=i
		end-if
		if Stop2 = 0 then
			Stop:=1
		end-if

until Stop=1

if Stop2 = 1 then
	forall(j in N)
		if j=Nodes and s=Nodes then
			write (d(j))
		else
			write (d(j),",")
		end-if
else
	write ("origin at node ",s," is not possible!")
end-if
writeln

end-do						!all-to-all
end-model