home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / ckscripts / shortestpath < prev    next >
Lisp/Scheme  |  2020-01-01  |  3KB  |  102 lines
  1. # Mind you C-Kermit is a communication software, not a toy language to
  2. # solve a chess problem.
  3. #
  4. # OK, let's talk computer network communication. One famous problem in
  5. # computer network is to find an optimal path from a source to a
  6. # destination. The path can be based on distance or transmit time, or ...
  7. # Following is the implementation of the Dijkstra's shortest path algorithm
  8. # through a graph of nodes.
  9. #
  10. # Reference: Andrew Tanenbaum, Computer Network.
  11. #
  12. # Dat Thuc Nguyen 20 Dec 2003
  13.  
  14. asg MAX_NODES 1024
  15. asg INFINITY 1000000000
  16.  
  17. declare \&p[MAX_NODES]                  # Predecessor node
  18. declare \&l[MAX_NODES]                  # Length between two nodes
  19. declare \&b[MAX_NODES]                  # Label markes path scanned
  20.  
  21. declare \&d[MAX_NODES*MAX_NODES]        # Distance from node i to j: \&d[e]
  22.  
  23. define shortest_path {
  24.     # \%1 source node
  25.     # \%2 destination node
  26.  
  27.     if > \%1 n { END -999 ERROR: Source node does not exist }
  28.     if > \%2 n { END -999 ERROR: Destination node does not exist }
  29.     if < \%1 0 { END -999 ERROR: Source node cannot be negativ }
  30.     if < \%2 0 { END -999 ERROR: Destination node cannot be negativ }
  31.  
  32.     for i 0 n-1 1 {
  33.         (setq \\&p[i] -1)
  34.         (setq \\&l[i] INFINITY)
  35.         (setq \\&b[i] 0)
  36.     }
  37.     (setq k \%2)                        # k is the initial working node
  38.     (setq \\&l[k] 0)                    # Destination length is zero
  39.     (setq \\&b[k] 1)                    # Destination node permanent
  40.  
  41.     while ( != k \%1 ) {
  42.  
  43.         for i 0 n-1 1 {
  44.             (setq e (+ (* k 10000) i))
  45.             if not define \&d[e] continue # skip non existing edge
  46.             (if ( AND \&d[e] (! \&b[i]) ( < (+ \&l[k] \&d[e]) \&l[i] )) 
  47.               (setq \\&p[i] k \\&l[i] (+ \&l[k] \&d[e]))
  48.              )
  49.         }
  50.         (setq k 0 smallest INFINITY)
  51.         for i 0 n-1 1 {
  52.             (if ( AND (! \&b[i]) (< \&l[i] smallest))
  53.               (setq smallest \&l[i] k i)
  54.              )
  55.         }
  56.         asg \&b[k] 1                    # Set permanent node on path
  57.     }
  58.     asg path ""
  59.     declare \&f[n]
  60.     (setq i 0 k \%1)
  61.     while ( >= k 0 ) {
  62.         (setq \\&f[i] k)
  63.         (++ i)
  64.         asg path "\m(path) \m(k)"
  65.         (setq k \&p[k])
  66.     }
  67.     echo Path found: \m(path)
  68. }
  69.  
  70. define node_node_distance {
  71.     # \%1 first node
  72.     # \%2 second node
  73.     # \%3 distance
  74.     (setq \\&d[\%1*10000+\%2] (setq \\&d[\%2*10000+\%1] \%3))
  75. }
  76.  
  77. (setq n 6)                              # Make a sample graph of 5 nodes...
  78.  
  79. # Node 0 connects with node 1, quality (distance, transmit time) is 110
  80. node_node_distance 0 1 110
  81.  
  82. # Node 0 connects with node 2, quality (distance, transmit time) is 120
  83. node_node_distance 0 2 120
  84.  
  85. # Node 1 connects with node 3, quality (distance, transmit time) is  75
  86. node_node_distance 1 3  75
  87.  
  88. # Node 2 connects with node 3, quality (distance, transmit time) is  85
  89. node_node_distance 2 3  85
  90.  
  91. # Node 3 connects with node 4, quality (distance, transmit time) is 185
  92. node_node_distance 3 4 185
  93.  
  94. # Node 1 connects with node 4, quality (distance, transmit time) is 885
  95. node_node_distance 1 4 885
  96.  
  97. # Find the shortest path between node 0 and node 4:
  98.  
  99. shortest_path 0 4
  100.  
  101. end
  102.