1 files changed, 73 insertions, 0 deletions
diff --git a/chapter25/docs/examples/Dijkstra.smp b/chapter25/docs/examples/Dijkstra.smp
new file mode 100644
index 00000000..57e1fad4
--- /dev/null
+++ b/chapter25/docs/examples/Dijkstra.smp
@@ -0,0 +1,73 @@
+// -*- mode: java;  -*-
+
+// 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();
+};