home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Columbia Kermit
/
kermit.zip
/
archives
/
ckscripts.tar.gz
/
ckscripts.tar
/
shortestpath
< prev
next >
Wrap
Lisp/Scheme
|
2003-12-20
|
3KB
|
102 lines
# 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