blob: fd595eb5769795cc2dc876fa86ad5b8c4c8550ba (
plain)
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
|
// An implementation of
// https://sampleprograms.io/projects/dijkstra/
val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst ->
i64 infinity = (1 << 63)-1;
var dist = new i64[nodes];
var visited = new sys.adt.bitset();
// All nodes are infinitely far from each other
for( int i=0; i<nodes; i++ ) dist[i] = infinity;
// Starting point is zero far from starting point
dist[src] = 0;
i64 result = -1;
int count = 0;
while( count < nodes && result < 0 ) {
int nearest = -1;
i64 best = infinity;
for( int node=0; node<nodes; node++ )
if( !visited.get(node) && dist[node] < best ) {
nearest = node;
best = dist[node];
}
if( nearest < 0 ) count = nodes;
else {
if( nearest == dst ) return best;
visited.set(nearest);
for( int node=0; node<nodes; node++ ) {
i64 weight = matrix.get(nearest*nodes + node);
if( weight > 0 && !visited.get(node) && best+weight < dist[node] )
dist[node] = best+weight;
}
}
count++;
}
return result;
};
val usage = { ->
sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n");
return 0;
};
val main = { u8[~][] args ->
// Exactly 3 args
if( args# != 4 ) return usage();
// First is a serialized square matrix of positive numbers
var matrix = sys.aryi64.parseAryI64(args[1]);
if( !matrix ) return usage();
if( !matrix.len ) return usage();
// All numbers are positive
for( int i=0; i<matrix.len; i++ )
if( matrix.get(i) < 0 ) return usage();
// Matrix is square
int nodes = 0;
while( nodes*nodes < matrix.len ) nodes++;
if( nodes*nodes != matrix.len )
return usage(); // Not a square matrix
// src,dst are values within the matrix
i64 src = sys.aryu8.atoi(args[2]);
i64 dst = sys.aryu8.atoi(args[3]);
if( src < 0 || src >= nodes || dst < 0 || dst >= nodes )
return usage(); // Source and destination land within the graph
i64 cost = shortestPath(matrix,nodes,src,dst);
if( cost >= 0 ) {
new sys.aryu8().num(cost).add('\n').write(1);
return 0;
}
return usage();
};
|
