267 lines
8.8 KiB
Plaintext
267 lines
8.8 KiB
Plaintext
/******************************************************/
|
||
/* This program finds the shortest path between nodes */
|
||
/* in a network. It has 8 internal procedures: */
|
||
/* SETUP, CONNECT, FIND, PRINT_ALL, PRINT_PATHS, */
|
||
/* SHORTEST_DISTANCE, PRINT_ROUTE, and FREE_ALL. */
|
||
/******************************************************/
|
||
network:
|
||
procedure options(main);
|
||
%replace
|
||
true by '1'b,
|
||
false by '0'b,
|
||
citysize by 20,
|
||
infinite by 32767;
|
||
declare
|
||
sysin file;
|
||
declare
|
||
1 city_node based,
|
||
2 city_name character(citysize) varying,
|
||
2 total_distance fixed,
|
||
2 investigate bit,
|
||
2 city_list pointer,
|
||
2 route_head pointer;
|
||
declare
|
||
1 route_node based,
|
||
2 next_city pointer,
|
||
2 route_distance fixed,
|
||
2 route_list pointer;
|
||
declare
|
||
city_head pointer;
|
||
|
||
do while(true);
|
||
call setup();
|
||
if city_head = null then
|
||
stop;
|
||
call print_all();
|
||
call print_paths();
|
||
call free_all();
|
||
end;
|
||
|
||
/******************************************************/
|
||
/* This procedure reads two cities and then calls the */
|
||
/* procedure CONNECT to establish the connection (in */
|
||
/* both directions) between the cities. */
|
||
/******************************************************/
|
||
setup:
|
||
procedure;
|
||
declare
|
||
distance fixed,
|
||
(city1, city2) character(citysize) varying;
|
||
on endfile(sysin) goto eof;
|
||
city_head = null;
|
||
put skip list('Type "City1, Dist, City2"');
|
||
put skip;
|
||
do while(true);
|
||
get list(city1, distance, city2);
|
||
call connect(city1, distance, city2);
|
||
call connect(city2, distance, city1);
|
||
end;
|
||
eof:
|
||
end setup;
|
||
|
||
/******************************************************/
|
||
/* This procedure establishes a single route_node to */
|
||
/* connect the first city to the second city by */
|
||
/* calling the FIND procedure twice; once for the */
|
||
/* first city and once for the second city. */
|
||
/******************************************************/
|
||
connect:
|
||
procedure(source_city, distance, destination_city);
|
||
declare
|
||
source_city character(citysize) varying,
|
||
destination_city character(citysize) varying,
|
||
distance fixed,
|
||
(r, s, d) pointer;
|
||
|
||
s = find(source_city);
|
||
d = find(destination_city);
|
||
allocate route_node set (r);
|
||
r->route_distance = distance;
|
||
r->next_city = d;
|
||
r->route_list = s->route_head;
|
||
s->route_head = r;
|
||
end connect;
|
||
|
||
/******************************************************/
|
||
/* This procedure searches the list of cities and */
|
||
/* returns a pointer to the requested city_node. */
|
||
/******************************************************/
|
||
find:
|
||
procedure(city) returns(pointer);
|
||
declare
|
||
city character(citysize) varying,
|
||
(p, q) pointer;
|
||
|
||
do p = city_head
|
||
repeat(p->city_list) while(p^=null);
|
||
if city = p->city_name then
|
||
return(p);
|
||
end;
|
||
allocate city_node set(p);
|
||
p->city_name = city;
|
||
p->city_list = city_head;
|
||
city_head = p;
|
||
p->total_distance = infinite;
|
||
p->route_head = null;
|
||
return(p);
|
||
end find;
|
||
|
||
/******************************************************/
|
||
/* This procedure starts at the city_head and displays*/
|
||
/* all the cities in the city_list. */
|
||
/******************************************************/
|
||
print_all:
|
||
procedure;
|
||
declare
|
||
(p, q) pointer;
|
||
|
||
do p = city_head
|
||
repeat(p->city_list) while(p^=null);
|
||
put skip list(p->city_name,':');
|
||
do q = p->route_head
|
||
repeat(q->route_list) while(q^=null);
|
||
put skip list(q->route_distance,'miles to',
|
||
q->next_city->city_name);
|
||
end;
|
||
end;
|
||
end print_all;
|
||
|
||
/******************************************************/
|
||
/* This procedure reads a destination city, calls the */
|
||
/* SHORTEST_DISTANCE procedure, and sets the */
|
||
/* total_distance field in each city_node to the */
|
||
/* total distance from the destination city. */
|
||
/******************************************************/
|
||
print_paths:
|
||
procedure;
|
||
declare
|
||
city character(citysize) varying;
|
||
|
||
on endfile(sysin) goto eof;
|
||
do while(true);
|
||
put skip list('Type Destination ');
|
||
get list(city);
|
||
call shortest_distance(city);
|
||
on endfile(sysin) goto eol;
|
||
do while(true);
|
||
put skip list('Type Start ');
|
||
get list(city);
|
||
call print_route(city);
|
||
end;
|
||
eol: revert endfile(sysin);
|
||
end;
|
||
eof:
|
||
end print_paths;
|
||
|
||
/******************************************************/
|
||
/* This procedure is the heart of the program. It */
|
||
/* takes an input city (the destination), and computes*/
|
||
/* the minimum total distance from every city in the */
|
||
/* network to the destination. It then records this */
|
||
/* minimum value in the total_distance field of every */
|
||
/* city_node. */
|
||
/******************************************************/
|
||
shortest_distance:
|
||
procedure(city);
|
||
declare
|
||
city character(citysize) varying;
|
||
declare
|
||
bestp pointer,
|
||
(d, bestd) fixed,
|
||
(p, q, r) pointer;
|
||
do p = city_head
|
||
repeat(p->city_list) while(p^=null);
|
||
p->total_distance = infinite;
|
||
p->investigate = false;
|
||
end;
|
||
p = find(city);
|
||
p->total_distance = 0;
|
||
p->investigate = true;
|
||
do while(true);
|
||
bestp = null;
|
||
bestd = infinite;
|
||
do p = city_head
|
||
repeat(p->city_list) while(p^=null);
|
||
if p->investigate then
|
||
do;
|
||
if p->total_distance < bestd then
|
||
do;
|
||
bestd = p->total_distance;
|
||
bestp = p;
|
||
end;
|
||
end;
|
||
end;
|
||
if bestp = null then
|
||
return;
|
||
bestp->investigate = false;
|
||
do q = bestp->route_head
|
||
repeat(q->route_list) while(q^=null);
|
||
r = q->next_city;
|
||
d = bestd + q->route_distance;
|
||
if d < r->total_distance then
|
||
do;
|
||
r->total_distance = d;
|
||
r->investigate = true;
|
||
end;
|
||
end;
|
||
end;
|
||
end shortest_distance;
|
||
|
||
/******************************************************/
|
||
/* This procedure displays the best route from the */
|
||
/* input city to the destination. */
|
||
/******************************************************/
|
||
print_route:
|
||
procedure(city);
|
||
declare
|
||
city character(citysize) varying;
|
||
declare
|
||
(p,q) pointer,
|
||
(t,d) fixed;
|
||
p = find(city);
|
||
do while(true);
|
||
t = p->total_distance;
|
||
if t = infinite then
|
||
do;
|
||
put skip list('(No Connection)');
|
||
return;
|
||
end;
|
||
if t = 0 then
|
||
return;
|
||
put skip list(t,'miles remain,');
|
||
q = p->route_head;
|
||
do while(q^=null);
|
||
p = q->next_city;
|
||
d = q->route_distance;
|
||
if t = d + p->total_distance then
|
||
do;
|
||
put list(d,'miles to',p->city_name);
|
||
q = null;
|
||
end;
|
||
else
|
||
q = q->route_list;
|
||
end;
|
||
end;
|
||
end print_route;
|
||
|
||
/******************************************************/
|
||
/* This procedure frees all the storage allocated */
|
||
/* by the program while processing the network. */
|
||
/******************************************************/
|
||
free_all:
|
||
procedure;
|
||
declare
|
||
(p, q) pointer;
|
||
do p = city_head
|
||
repeat(p->city_list) while(p^=null);
|
||
do q = p->route_head
|
||
repeat(q->route_list) while(q^=null);
|
||
free q->route_node;
|
||
end;
|
||
free p->city_node;
|
||
end;
|
||
end free_all;
|
||
|
||
end network;
|
||
|
||
|