-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.janus
311 lines (278 loc) · 10.8 KB
/
dijkstra.janus
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
/*
* Dijkstra's Algorithm
* Implement with a weighted adjacency graph with extra node information
*/
/******* Heaps data structure *******/
procedure decreasekey(int A[], int i, int key,
int garbage[], int garbagecounters[], int dcnt,
int nodes[])
local int tmp = i
if key > nodes[A[i]-1][2] then
error("New key is bigger than current key")
fi key > nodes[A[i]-1][2]
garbage[dcnt][0] += nodes[A[i]-1][2] - key
nodes[A[i]-1][2] -= garbage[dcnt][0]
local int loopcond = 1
from loopcond = 1 && garbagecounters[dcnt] = 0 do
garbagecounters[dcnt] += 1
local int parent = 0
call parent(tmp, parent)
garbage[dcnt][garbagecounters[dcnt]] += tmp
if tmp <= 1 || nodes[A[parent]-1][2] <= nodes[A[tmp]-1][2] then
loopcond -= 1
else
A[tmp] <=> A[parent]
tmp -= garbage[dcnt][garbagecounters[dcnt]]
tmp += parent
fi loopcond = 0
uncall parent(garbage[dcnt][garbagecounters[dcnt]], parent)
delocal int parent = 0
until loopcond = 0
delocal int loopcond = 0
delocal int tmp = garbage[dcnt][garbagecounters[dcnt]]
procedure extractmin(int A[], int heapsize, int min, int nodes[],
int heapgarbage[], int garbagei)
if heapsize < 1 then
error("Heap underflow")
fi heapsize < 1
min += A[1]
A[1] <=> A[heapsize]
heapsize -= 1
local int garbagecounter = 0
call minheapify(A, heapsize, 1, nodes,
heapgarbage, garbagecounter, garbagei)
delocal int garbagecounter = 0
garbagei += 1
procedure minheapify(int A[], int heapsize, int i, int nodes[],
int heapgarbage[], int garbagecounter, int garbagei)
local int left = 0, int right = 0, int min = 0
call left(i, left)
call right(i, right)
if left <= heapsize && nodes[A[left]-1][2] < nodes[A[i]-1][2] then
min += left
if right <= heapsize && nodes[A[right]-1][2] < nodes[A[min]-1][2] then
min -= left
min += right
fi right <= heapsize && nodes[A[right]-1][2] < nodes[A[left]-1][2]
else
min += i
if right <= heapsize && nodes[A[right]-1][2] < nodes[A[min]-1][2] then
min -= i
min += right
fi right <= heapsize && nodes[A[right]-1][2] < nodes[A[i]-1][2]
fi left <= heapsize && nodes[A[left]-1][2] < nodes[A[i]-1][2]
heapgarbage[garbagei][garbagecounter] += min
garbagecounter += 1
if min != i then
A[i] <=> A[min]
call minheapify(A, heapsize, min, nodes,
heapgarbage, garbagecounter, garbagei)
if left = heapgarbage[garbagei][garbagecounter-1] then
min -= left
else
min -= right
fi left = heapgarbage[garbagei][garbagecounter-1]
fi min = 0
garbagecounter -= 1
if i = heapgarbage[garbagei][garbagecounter] then
min -= i
fi i = heapgarbage[garbagei][garbagecounter]
uncall right(i, right)
uncall left(i, left)
delocal int left = 0, int right = 0, int min = 0
procedure parent(int i, int parent)
parent += i / 2
procedure left(int i, int left)
left += 2 * i
procedure right(int i, int right)
right += 2 * i + 1
/******** End heap data structure *******/
/******* ADJACENCY LIST FUNCTIONS START *******/
/*
* getlist gets the contents of a single list in the adjacency list.
*
* Parameters:
* int adjacent[] A list of adjacency list elements
* int ptrs[] A list of pointers to the start of each individual list
* int i The list that should get extracted (numbered)
* int res[] A list to store the returned elements in
*
* Returns:
* A copy of a the items in a list in the adjacency list.
*/
procedure getlist(int adjacent[], int ptrs[], int i, int res[])
// end contains a pointer to the end of the wanted list
local int end = 0
if i = (size(ptrs) - 1) then
// If we try to get the last list we stop at the end of the element list
end += size(adjacent)
else
// Or else, we stop where the next list starts
end += ptrs[i + 1][0]
fi i = (size(ptrs) - 1)
// All elements of the wanted list are loaded into res
local int r = ptrs[i][0]
from r = ptrs[i][0] do
res[r - ptrs[i][0]] += adjacent[r][0]
r += 1
until r = end
delocal int r = end
// end is delocated
if i = (size(ptrs) - 1) then
end -= size(adjacent)
else
end -= ptrs[i + 1][0]
fi i = (size(ptrs) - 1)
delocal int end = 0
/******** ADJACENCY LIST FUNCTIONS END ********/
/* initialize initiates the tree's nodes to have no parent and their
* shortest-path estimates to infinity (4294967295). It then sets the source
* nodes path estimate to be 0.
*/
procedure initialize(int nodes[], int queue[], int s)
local int i = 2, int n = 1
nodes[s-1][1] -= 1
queue[1] += s
from i = 2 do
if i = s + 1 then
n += 1
fi i = s + 1
nodes[n-1][1] -= 1
nodes[n-1][2] += 4294967295
queue[i] += n
n += 1
i += 1
until i = size(nodes) + 1
delocal int i = size(nodes) + 1, int n = size(nodes) + 1
/* relax relaxes an edge between the nodes u and v.
*
* Parameters:
* int u Index of first node
* int v Index of second node
* int nodes[] A list of all nodes
* int weight The weight between the two nodes
* int relaxgarbage[] Empty garbage arrays for each call to relax
* int relaxcounters[] Empty garbage array for each call to relax
* int queue[] A minimum priority queue containing nodes waiting
* int queuesize The current size of the queue
* int count Pointer for decreasekey, initialized to 0
* int adjacentgarbage[] Empty garbage arrays for each call to decreasekey
*
* Post conditions:
* The edge between u and v has been relaxed, and u has (possibly) been updated
* with a new weight.
*/
procedure relax(int u, int v, int nodes[], int weight,
int relaxgarbage[], int relaxcounters[],
int queue[], int queuesize,
int count, int adjacentgarbage[])
local int i = 0
from i = 0 do
if queue[i+1] = v then
adjacentgarbage[count][0] += i + 1
count += 1
fi queue[i+1] = v
i += 1
until i = queuesize
delocal int i = queuesize
if nodes[v-1][2] > nodes[u-1][2] + weight then
call decreasekey(queue, adjacentgarbage[count-1][0], nodes[u-1][2] + weight,
relaxgarbage, relaxcounters, count-1, nodes)
nodes[v-1][1] <=> adjacentgarbage[count][1]
nodes[v-1][1] += u
fi nodes[v-1][2] = nodes[u-1][2] + weight
/* getadjsize finds the size of the adjacency list belonging to a single node
*
* int u Index of the node
* int nodes[] Array containing all nodes
* int G[] List of adjaceny nodes
* int return Return value (initially 0)
*
* Post condition:
* return contains the amount of nodes adjacent to u
*/
procedure getadjsize(int u, int nodes[], int G[], int return)
if u < size(nodes) then
return += nodes[u][0]-nodes[u-1][0]
else
return += size(G)-nodes[u-1][0]
fi u < size(nodes)
/* joinset adds the current value of node u to its corresponding place in a set.
*
* Parameters:
* int set[] The set that node u should be added to
* int u The index of node u
* int nodes[] A list of nodes with node information
*/
procedure joinset(int set[], int u, int nodes[])
set[u][0] += nodes[u][0]
set[u][1] += nodes[u][1]
set[u][2] += nodes[u][2]
/* dijkstra finds the shortest paths to all nodes in a graph G from a source s.
* Uses an adjacency list with an added key to represent the graph.
*
* int G[] An adjacency matrix representing G
* int nodes[] Nodes of the graph G
* int a Index for the source of the tree
* int queue[] Empty garbage arrays for each call to extractmin
* int relaxgarbage[] Empty garbage arrays for each call to relax
* int relaxcounters[] Empty garbage array for each call to relax
* int extractgarbage[] Empty garbage arrays for each call to extractmin
* int count Pointer for decreasekey, initialized to 0
* int adjacentgarbage[] Empty garbage arrays for each call to decreasekey
*
* Post conditions:
* nodes[] contains a shortest path graph for the graph G
*/
procedure dijkstra(int G[], int nodes[], int s, int queue[],
int relaxgarbage[], int relaxcounters[], int extractgarbage[],
int count, int adjacentgarbage[])
local int queuesize = size(queue) - 1, int extractcounter = 0
call initialize(nodes, queue, s)
from queuesize = size(queue)-1 do
local int u = 0, int adjsize = 0
call extractmin(queue, queuesize, u, nodes,
extractgarbage, extractcounter)
call getadjsize(u, nodes, G, adjsize)
local int adjlist[adjsize] = {0}
call getlist(G, nodes, u-1, adjlist)
local int i = 0
from i = 0 do
if queuesize != 0 then
local int weight = G[nodes[u-1][0]+i][1]
call relax(u, adjlist[i], nodes, weight,
relaxgarbage, relaxcounters, queue, queuesize,
count, adjacentgarbage)
delocal int weight = G[nodes[u-1][0]+i][1]
fi queuesize != 0
i += 1
until i = size(adjlist)
delocal int i = size(adjlist)
uncall getlist(G, nodes, u-1, adjlist)
delocal int adjlist[adjsize] = {0}
uncall getadjsize(u, nodes, G, adjsize)
delocal int u = queue[queuesize+1], int adjsize = 0
until queuesize = 0
delocal int queuesize = 0, int extractcounter = size(nodes)
procedure main()
// Graph with 5 nodes represented as an adjacency list
int G[10][2] = {{2, 2}, {4, 5},
{1, 2}, {5, 4},
{4, 4},
{1, 5}, {3, 4}, {5, 7},
{2, 4}, {4, 7}}
int nodes[5][3] = {{0, 0, 0},
{2, 0, 0},
{4, 0, 0},
{5, 0, 0},
{8, 0, 0}}
int queuegarbage[size(nodes)+1]
int relaxgarbage[size(nodes)][(size(nodes)+3)/2]
int relaxcounters[size(nodes)]
int extractgarbage[size(nodes)][(size(nodes)+1)/2]
int count
int adjacentgarbage[size(G)][2]
printf("")
call dijkstra(G, nodes, 3, queuegarbage,
relaxgarbage, relaxcounters, extractgarbage,
count, adjacentgarbage)