# Mind you C-Kermit is a communication software, not a toy language to
# solve a chess problem.
#
# OK, let's talk computer network communication. One famous problem in
# computer network is to find an optimal path from a source to a
# destination. The path can be based on distance or transmit time, or ...
# Following is the implementation of the Dijkstra's shortest path algorithm
# through a graph of nodes.
#
# Reference: Andrew Tanenbaum, Computer Network.
#
# Dat Thuc Nguyen 20 Dec 2003

asg MAX_NODES 1024
asg INFINITY 1000000000

declare \&p[MAX_NODES]                  # Predecessor node
declare \&l[MAX_NODES]                  # Length between two nodes
declare \&b[MAX_NODES]                  # Label markes path scanned

declare \&d[MAX_NODES*MAX_NODES]        # Distance from node i to j: \&d[e]

define shortest_path {
    # \%1 source node
    # \%2 destination node

    if > \%1 n { END -999 ERROR: Source node does not exist }
    if > \%2 n { END -999 ERROR: Destination node does not exist }
    if < \%1 0 { END -999 ERROR: Source node cannot be negativ }
    if < \%2 0 { END -999 ERROR: Destination node cannot be negativ }

    for i 0 n-1 1 {
        (setq \\&p[i] -1)
        (setq \\&l[i] INFINITY)
        (setq \\&b[i] 0)
    }
    (setq k \%2)                        # k is the initial working node
    (setq \\&l[k] 0)                    # Destination length is zero
    (setq \\&b[k] 1)                    # Destination node permanent

    while ( != k \%1 ) {

        for i 0 n-1 1 {
            (setq e (+ (* k 10000) i))
            if not define \&d[e] continue # skip non existing edge
            (if ( AND \&d[e] (! \&b[i]) ( < (+ \&l[k] \&d[e]) \&l[i] )) 
              (setq \\&p[i] k \\&l[i] (+ \&l[k] \&d[e]))
             )
        }
        (setq k 0 smallest INFINITY)
        for i 0 n-1 1 {
            (if ( AND (! \&b[i]) (< \&l[i] smallest))
              (setq smallest \&l[i] k i)
             )
        }
        asg \&b[k] 1                    # Set permanent node on path
    }
    asg path ""
    declare \&f[n]
    (setq i 0 k \%1)
    while ( >= k 0 ) {
        (setq \\&f[i] k)
        (++ i)
        asg path "\m(path) \m(k)"
        (setq k \&p[k])
    }
    echo Path found: \m(path)
}

define node_node_distance {
    # \%1 first node
    # \%2 second node
    # \%3 distance
    (setq \\&d[\%1*10000+\%2] (setq \\&d[\%2*10000+\%1] \%3))
}

(setq n 6)                              # Make a sample graph of 5 nodes...

# Node 0 connects with node 1, quality (distance, transmit time) is 110
node_node_distance 0 1 110

# Node 0 connects with node 2, quality (distance, transmit time) is 120
node_node_distance 0 2 120

# Node 1 connects with node 3, quality (distance, transmit time) is  75
node_node_distance 1 3  75

# Node 2 connects with node 3, quality (distance, transmit time) is  85
node_node_distance 2 3  85

# Node 3 connects with node 4, quality (distance, transmit time) is 185
node_node_distance 3 4 185

# Node 1 connects with node 4, quality (distance, transmit time) is 885
node_node_distance 1 4 885

# Find the shortest path between node 0 and node 4:

shortest_path 0 4

end