home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Columbia Kermit
/
kermit.zip
/
ckscripts
/
shortest_path
< prev
next >
Wrap
Lisp/Scheme
|
2020-01-01
|
7KB
|
239 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 node_list "#"
define node_node_distance {
# \%1 first node
# \%2 second node
# \%3 distance
asg \%1 \flower(\%1)
asg \%2 \flower(\%2)
echo {Add node \%1 and node \%2 distance \%3}
if = 0 \findex({#\%1#},\m(node_list)) { # first node exists in graph?
asg node_list {\m(node_list)\%1#}
}
if = 0 \findex({#\%2#},\m(node_list)) { # second node exists in graph?
asg node_list {\m(node_list)\%2#}
}
(setq d_\%1_\%2 (setq d_\%2_\%1 \%3))
}
define remove_node {
# \%1, \%2, ... node to be removed
local parms
for i 1 \v(argc)-1 1 {
asg parms \m(parms) \&_[i]
}
disable_node \m(parms)
detach_node \m(parms)
}
define enable_node {
local parms
for i 1 \v(argc)-1 1 {
if = \findex({#\%1#},\m(node_list)) 0 {
asg node_list {\m(node_list)\&_[i]#}
}
asg parms \m(parms) \&_[i]
}
echo enable node: \m(parms)
}
define disable_node {
local parms
for i 1 \v(argc)-1 1 {
if > \findex({#\&_[i]#},\m(node_list)) 0 {
asg node_list \freplace(\m(node_list),{#\&_[i]#},#)
}
asg parms \m(parms) \&_[i]
}
echo disable node: \m(parms)
}
define detach_node {
local parms
for i 1 \v(argc)-1 1 {
asg parms \m(parms) \&_[i]
graph_dim
for j 1 ll 1 { # disconnect with other nodes
if define \m(d_\&s[j]_\&_[i]) {
detach_edge \&s[j] \&_[i]
}
}
}
echo detach node: \m(parms)
}
define detach_edge {
# \%1 first node
# \%2 second node
(setq d_\%1_\%2)
(setq d_\%2_\%1)
}
define graph_dim {
local \&a \&b nodenum j n
asg n \faaconvert(node,&a,&b)
asg n \faaconvert(vertex,&a,&b)
asg nodenum 0
array declare \&s[]
asg ll \fsplit(\m(node_list),&s,#)
for j 1 ll 1 {
(++ nodenum)
(setq node<\&s[j]> \m(nodenum))
(setq vertex<\m(nodenum)> '\&s[j])
}
}
define shortest_path {
# \%1 source node
# \%2 destination node
echo
echo {Search shortest path from \%1 to \%2}
asg \%1 \flower(\%1)
asg \%2 \flower(\%2)
if = 0 \findex(\%1,\m(node_list)) END -999 Source node \%1 does not exist
if = 0 \findex(\%2,\m(node_list)) END -999 Destination node \%2 not exist
graph_dim
local \&p[] \&l[] \&b[] INFINITY
declare \&p[ll] # Predecessor node
declare \&l[ll] # Length between two nodes
declare \&b[ll] # Label markes path scanned
asg INFINITY 1000000000
local i j h k d_k_i n1 n2
for j 1 ll 1 {
(setq i node<\&s[j]>)
(setq \\&p[i] -1)
(setq \\&l[i] INFINITY)
(setq \\&b[i] 0)
}
asg n1 \%1
asg n2 \%2
asg \%1 \m(node<\%1>)
asg \%2 \m(node<\%2>)
(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 ) {
(setq h k) # To identify non existing path (run in cycle)
for j 1 ll 1 {
(setq i node<\&s[j]>)
asg vk \freplace(\m(vertex<\m(k)>),',)
asg vi \freplace(\m(vertex<\m(i)>),',)
if not define \m(d_\m(vk)_\m(vi)) continue # Skip non existing edge
asg d_k_i \m(d_\m(vk)_\m(vi))
(if ( AND d_k_i (! \&b[i]) ( < (+ \&l[k] d_k_i) \&l[i] ))
(setq \\&p[i] k \\&l[i] (+ \&l[k] d_k_i))
)
}
(setq k 0 smallest INFINITY)
for j 1 ll 1 {
(setq i node<\&s[j]>)
(if ( AND (! \&b[i]) (< \&l[i] smallest))
(setq smallest \&l[i] k i)
)
}
if == h k END -999 * No path found between \m(n1) and \m(n2) *
asg \&b[k] 1 # Set permanent node on path
}
echo
local path dist
asg path "-"
asg dist 0
(setq k \%1)
while true {
asg path "\m(path) \m(vertex<\m(k)>) -"
(setq from k)
(setq k \&p[k] to k)
if < k 0 break
asg vk \freplace(\m(vertex<\m(from)>),',)
asg vi \freplace(\m(vertex<\m(to)>),',)
asg d_k_i \m(d_\m(vk)_\m(vi))
asg msg {from \m(vertex<\m(from)>) to -
\m(vertex<\m(to)>), distance: \m(d_k_i)}
echo \freplace(\m(msg),',)
(++ dist d_k_i)
}
if > \m(dist) 0 {
echo {Path found: \freplace(\m(path),',), total distance: \m(dist)}
} else {
END -999 ** No Path found between \m(vertex<n1>) and \m(vertex<n2>) **
}
echo
}
# Make a sample graph
# 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 230
node_node_distance 0 2 230
# Node 0 connects with node 9, quality (distance, transmit time) is 120
node_node_distance 0 9 120
# Node 1 connects with node 3, quality (distance, transmit time) is 75
node_node_distance 1 3 75
# Node 1 connects with node 2, quality (distance, transmit time) is 50
node_node_distance 1 2 50
# 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
# Node 4 connects with node 5, quality (distance, transmit time) is 325
node_node_distance 4 5 325
# Node 2 connects with node 5, quality (distance, transmit time) is 25
node_node_distance 2 5 25
# Node 5 connects with node 7, quality (distance, transmit time) is 325
node_node_distance 5 7 325
# City Paris connects with London, quality (distance, transmit time) is 600
node_node_distance Paris London 600
# City Paris connects with Athen, quality (distance, transmit time) is 2000
node_node_distance Paris Athen 2000
# City Athen connects with Macao, quality (distance, transmit time) is 2500
node_node_distance Athen Macao 2500
# Find the shortest path between node 0 and node 4:
shortest_path 0 4
# Find the shortest path between Paris and Macao
shortest_path Paris Macao
end