home *** CD-ROM | disk | FTP | other *** search
/ kermit.columbia.edu / kermit.columbia.edu.tar / kermit.columbia.edu / scripts / ckermit / shortestpath.~1~ < prev    next >
Lisp/Scheme  |  2003-12-19  |  3KB  |  100 lines
  1. # Mind you C-Kermit is a communication software, not a toy language to
  2. # solve a chess problem.
  3. # OK, let's talk computer network communication. One famous problem in
  4. # computer network is to find an optimal path from a source to a
  5. # destination. The path can be based on distance or transmit time, or ...
  6. # Following is the implementation of the Dijkstra's shortest path algorithm
  7. # through a graph of nodes.
  8. # Reference: Andrew Tanenbaum, Computer Network.
  9. #
  10. # Dat Thuc Nguyen 20 Dec 2003
  11.  
  12. asg MAX_NODES 1024
  13. asg INFINITY 1000000000
  14.  
  15. declare \&p[MAX_NODES]            # predecessor node
  16. declare \&l[MAX_NODES]            # length between two nodes
  17. declare \&b[MAX_NODES]            # label markes path scanned
  18.  
  19. declare \&d[MAX_NODES*MAX_NODES]    # distance from node i to j: \&d[e]
  20.  
  21. define shortest_path {
  22.     # \%1 source node
  23.     # \%2 destination node
  24.  
  25.     if > \%1 n { END -999 ERROR: Source node does not exist }
  26.     if > \%2 n { END -999 ERROR: Destination node does not exist }
  27.     if < \%1 0 { END -999 ERROR: Source node cannot be negativ }
  28.     if < \%2 0 { END -999 ERROR: Destination node cannot be negativ }
  29.  
  30.     for i 0 n-1 1 {
  31.         (setq \\&p[i] -1)
  32.         (setq \\&l[i] INFINITY)
  33.         (setq \\&b[i] 0)
  34.     }
  35.  
  36.     (setq k \%2)            # k is the initial working node
  37.     (setq \\&l[k] 0)                    # destination length is zero
  38.     (setq \\&b[k] 1)                    # destination node permanent
  39.  
  40.     while ( != k \%1 ) {
  41.  
  42.         for i 0 n-1 1 {
  43.             (setq e (+ (* k 10000) i))
  44.             if not define \&d[e] continue # skip non existing edge
  45.             (if ( AND \&d[e] (! \&b[i]) ( < (+ \&l[k] \&d[e]) \&l[i] )) 
  46.               (setq \\&p[i] k \\&l[i] (+ \&l[k] \&d[e]))
  47.              )
  48.         }
  49.         (setq k 0 smallest INFINITY)
  50.         for i 0 n-1 1 {
  51.             (if ( AND (! \&b[i]) (< \&l[i] smallest))
  52.               (setq smallest \&l[i] k i)
  53.              )
  54.         }
  55.         asg \&b[k] 1                    # set permanent node on path
  56.     }
  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)                              # This is 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. shortest_path 0 4           # Find the shortest path between node 0 and node 4
  98.  
  99. end
  100.