# 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