Jay PedersenUniversity of Nebraska at Omaha student
2005-05-12
Project: Implement Dijkstras Algorithm for determining shortest paths in a network This is a well-known algorithm. One place where it is defined is in 'Network Flows' by Ravindra Ahuga, Thomas Magnanti, and James Orlin, (c) 1993, ISBN 0-13-617549-X. Storage of a network is done into a 'Forward Star' and 'Reverse Star' data structure. These structures are also defined in 'Network Flows' in section 2.3 (Network Representations). Maple programming is described in "maple 9; Introductory Programming Guide" from Maplesoft; ISBN 189451143-3. Available from the maplesoft website. Notes: global variables have the first character in upper-case, eg: NodeCount.Input: The algorithm takes as input a text file which contains one ore more network definitions.
The assumption is made that nodes are numberd 1:N, where N is the number of nodes. 1. A network definition begins with a '#START' line. 2. Following this a line containing the number of nodes in the network,
the number of arcs in the network and the source node. For example: 4,7,5 defines a network with 4 nodes and 7 arcs
and says that node 5 is the source node to find shortest paths from. 3. Following this is a series of lines, one per arc in the network, which define the arcs in the network. Each line contains the start node, end node and cost of traveling the arc. For example: 2,5,15 defines an arc from 2 to 5 with cost 15. The definition ends with a '#END' line. Example network definion (4 nodes, 6 arcs, source node is 1): #START
4 6 1
1 2 1
1 3 3
2 3 2
3 2 4
2 4 5
3 4 9 #END Many networks can be defined in a single file by using multiple #START : #END sequences.Usage: The subroutine Dijkstras_Algorithm is invoked to determine the shortest paths on the networks defined in the text file.
The code can optionally create a graph of the shortest paths of the last network in the file. Specifying the make_graph argument as true will make global variable G contain a graph. The Maple statement 'draw(G)'
can then be used to show a graphical representation of the shortest paths.
Example usage (process graphs in "test1.txt"):
Dijstras_Algorithm("test1.txt", true);
draw(G); # graphical representation of shortest pathsrestart;
with(networks):# Routine: LoadNetworkFile
# Abstract: Reads network definition file and loads into
# a Forward Star data structure
#
# File assumed open with file descriptor FileDesc,
# if EOF reached before any data ... exit cleanly.
#
# Arguments: none
# Input: FileDesc - file opened for input
# Output: NodeCount, ArcCount,
# SourceNode, SinkNode,
# FS_tail, FS_head, FS_cost
# FS_point, FS_rpoint, FS_trace
# Returns: boolean, true if valid network found and loaded
#
# File syntax: (1) comment Lines - lines beginning with '#'
# 1st Data Line -
# node count, arc count, source node
# 2nd : nth Data Lines (arc definitions)
# from node #, to node #, arc cost
loadNetworkFile := proc ()
local s, all_done, result, first_dataline_read,
file_data, arc_number,
raw_tail, raw_head, raw_cost,
node_num, arc_num;
global FileDesc, NodeCount, ArcCount, SourceNode,
FS_point, FS_tail, FS_head, FS_cost,
FS_trace, FS_rpoint;
# initialize
result := true;
all_done := false;
first_dataline_read := false;
arc_number := 0;
# read file
while (not all_done) do;
s := readline(FileDesc);
if (s = 0) then # EOF
all_done := true;
fclose(FileDesc);
if (not first_dataline_read) then
NodeCount := 0; # indicate EOF condition
ArcCount := 0;
return true; # clean exit, no more definitions
end if;
elif (length(s) = 0) then
; # ignore blank line
elif (s = "#END") then # end of this definition
all_done := true;
elif (s[1] = "#") then
; # ignore comment line
else
if (not first_dataline_read) then
# number of nodes, number of arcs, source, sink
file_data := sscanf(s, "%d %d %d %d");
if (file_data = 0) then # parse error
all_done := true;
elif (nops(file_data) <> 3) then # parse error
all_done := true;
elif ((file_data[1] < 1) or (file_data[2] < 1) or
(file_data[3] < 1) or (file_data[3] > file_data[1])) then
all_done := true;
end if;
if (all_done) then
result := false;
printf("Invalid data: %s\n", s);
printf("Possibly invalid NodeCount, ArcCount, SourceNode, SinkNode\n");
else
NodeCount := file_data[1];
ArcCount := file_data[2];
SourceNode := file_data[3];
raw_tail := array(1..ArcCount);
raw_head := array(1..ArcCount);
raw_cost := array(1..ArcCount);
FS_point := array(1..NodeCount+1);
FS_tail := array(1..ArcCount);
FS_head := array(1..ArcCount);
FS_cost := array(1..ArcCount);
FS_trace := array(1..ArcCount);
FS_rpoint := array(1..NodeCount+1);
first_dataline_read := true;
end if;
else
# arc definition - from node, to node, cost, arc capacity
arc_number := arc_number + 1;
if (arc_number > ArcCount) then
printf("Invalid data: too many arc definitions, > %d\n",
ArcCount);
all_done := true;
result := false;
else
file_data := sscanf(s, "%d %d %d");
if (file_data = 0) then # EOF
all_done := true:
elif (nops(file_data) <> 3) then
all_done := true;
elif ((file_data[1] < 1) or (file_data[1] > NodeCount) or
(file_data[2] < 1) or (file_data[2] > NodeCount) or
(file_data[3] < 0)) then
all_done := true;
end if;
if (all_done) then
result := false;
printf("Invalid arc definition: %s\n", s);
printf("Possibly invalid node number or cost\n");
else
raw_tail[arc_number] := file_data[1];
raw_head[arc_number] := file_data[2];
raw_cost[arc_number] := file_data[3];
end if;
end if;
end if;
end if;
end;
# validation of data
if (result = true) then
if (arc_number <> ArcCount) then
printf("Invalid data: wrong number of arc definions, %d <> %d\n",
arc_number, ArcCount);
result := FALSE;
end if;
end if;
# Load into forward-star data structure
if (result = true) then
# forward-direction, arcs emanating from node i
arc_number := 0;
for node_num to NodeCount do;
FS_point[node_num] := arc_number + 1;
for arc_num to ArcCount do;
if (raw_tail[arc_num] = node_num) then
arc_number := arc_number + 1;
FS_tail[arc_number] := raw_tail[arc_num];
FS_head[arc_number] := raw_head[arc_num];
FS_cost[arc_number] := raw_cost[arc_num];
end if;
end;
end;
FS_point[NodeCount+1] := ArcCount + 1;
# reverse-direction, arcs coming into node i
arc_number := 0;
for node_num to NodeCount do;
FS_rpoint[node_num] := arc_number + 1;
for arc_num to ArcCount do;
if (FS_head[arc_num] = node_num) then
arc_number := arc_number + 1;
FS_trace[arc_number] := arc_num;
end if;
end;
end;
FS_rpoint[NodeCount+1] := ArcCount + 1;
end if;
# all done
return result;
end proc: # loadNetworkFile# Routine: ShowArcs
# Abstract: Display Arcs in network, debugging routine
# example of manipulating forward-star structure
# Arguments: none
# Input: Forward-Star network defintion, vbls FS_x
# Output: Display to screen
ShowArcs := proc()
local node_num, arc_num;
global NodeCount, ArcCount,
FS_point, FS_tail, FS_head,
FS_trace, FS_rpoint;
printf("Forward arcs:\n\n");
for node_num to NodeCount do;
printf ("From %d:\n", node_num);
for arc_num from FS_point[node_num] to
(FS_point[node_num+1] - 1) do;
printf("%d. %d - %d\n",
arc_num, FS_tail[arc_num],
FS_head[arc_num]);
end;
end;
printf("\nBackward arcs:\n\n");
for node_num to NodeCount do;
printf("To %d:\n", node_num);
for arc_num from FS_rpoint[node_num] to
(FS_rpoint[node_num+1]-1) do;
printf("%d. %d - %d\n",
arc_num, FS_tail[FS_trace[arc_num]],
FS_head[FS_trace[arc_num]]);
end;
end;
# all done
return true;
end proc: # ShowArcsDijkstras_Algorithm := proc (target_filename::string, make_graph::boolean)
local s :: set, dist, pred, i :: integer, j :: integer,
in_S :: integer, graph_count :: integer,
arc_num :: integer, testval :: integer, found_one :: boolean,
result :: boolean, sink :: integer;
global NodeCount, ArcCount, FS_tail, FS_head, FS_cost,
FS_point, FS_rpoint, FS_trace, G, FileDesc;
# open file (exits procedure if fails)
FileDesc := fopen(target_filename, READ, TEXT);
graph_count := 0;
do
# read network definition
result := loadNetworkFile();
if (not result) then
return result; # false
elif (NodeCount = 0) then # EOF
return true; # clean exit
end if;
graph_count := graph_count + 1;
# create necessary arrays
pred := array(1..NodeCount, [seq(0,i=1..NodeCount)]); # predecessor of each node
dist := array(1..NodeCount, [seq(infinity,i=1..NodeCount)]); # dist to of each node
# process
i := SourceNode; dist[i] := 0; pred[i] := 0; in_S := 0; s := { };
while (in_S < NodeCount) do
# find minimum distance node, not in s
found_one := false;
for j to NodeCount do;
if ((dist[j] <> infinity) and (not (j in s))) then
if (not found_one) then
found_one := true;
i := j;
testval := dist[j];
elif (dist[j] < testval) then
i := j;
testval := dist[j];
end if;
end if;
end;
# sanity check
if (not found_one) then
printf("Aborting Dijkstras Algorithm, next node not determined.\n");
printf("Network : %d\n", graph_count);
printf("Possible network definition issue, fully connected?\n");
return false;
end if;
# add next item to list
s := s union { i };
in_S := in_S + 1;
sink := i;
# process all arcs emanating from i
for arc_num from FS_point[i] to
(FS_point[i+1] - 1) do;
j := FS_head[arc_num];
if (not (j in s)) then
testval := dist[i] + FS_cost[arc_num];
if (testval < dist[j]) then
dist[j] := testval;
pred[j] := i;
end if;
end if;
end;
end; # while (in_S < NodeCount)
# At this point, shortest paths for graph is determined.
printf("\nGraph %d shortest paths from node %d:\n\n",
graph_count, SourceNode);
printf(" Node Dist Prev\n");
for i to NodeCount do;
if (i <> SourceNode) then
printf ("%6d %6d %6d\n", i, dist[i], pred[i]);
end if;
end;
printf("\n");
# create graph G if requested
if (make_graph) then
new(G):
addvertex(seq(i,i=1..NodeCount),G);
for i to NodeCount do;
if (i <> SourceNode) then
j := pred[i];
connect({i},{j},G);
end if;
end;
end if;
end;
return true;
end proc: # Dijkstras_Algorithm
# test
Dijkstras_Algorithm("test1.txt", true);draw(G);