<Text-field style="Heading 1" layout="Heading 1"><Font family="Arial">References</Font></Text-field>

<Text-field style="Heading 1" layout="Heading 1"><Font family="Arial">Algorithm Code</Font></Text-field>

Dijkstras_Shortest_Path := module() # Note: global variables started with uppercase, eg: ArcCount # Note: 'for i to n' means 'for i from 1 to n' option package; export Dijkstras_Algorithm; local loadNetwork, ShowArcs; # internal support routines Dijkstras_Algorithm := proc (network_def::list) local s :: set, dist, pred, i :: integer, j :: integer, in_S :: integer, arc_num :: integer, testval :: integer, found_one :: boolean, result :: boolean, sink :: integer, make_graph :: boolean; global NodeCount, ArcCount, FS_tail, FS_head, FS_cost, FS_point, FS_rpoint, FS_trace, G; # determine if 2nd argument passed and set true => generate graph make_graph := evalb(nargs = 2 and type(args[2],boolean) and args[2]); # process network definition, load Forward-Star result := loadNetwork(network_def); if (not result) then return false; end if; # create and init 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 network, find shortest path from source to destintions 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.\134n"); printf("Possible network definition issue, not fully connected?\134n"); 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("\134nshortest paths from source (from node %d):\134n\134n", SourceNode); printf(" To Node Dist Prev Node\134n"); for i to NodeCount do; if (i <> SourceNode) then printf (" %6d %6d %6d\134n", i, dist[i], pred[i]); end if; end; printf("\134n"); # 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; return(draw(G)); end if; return true; end proc: # Dijkstras_Algorithm # Routine: LoadNetwork # Abstract: Reads network definition from string and loads # into Forward Start data structure. # Arguments: s - string containing network definition # 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 loadNetwork := proc (Network_def::list) local n, s, src, all_done, result, first_seq, seq_data, arc_number, raw_tail, raw_head, raw_cost, node_num, arc_num; global NodeCount, ArcCount, SourceNode, FS_point, FS_tail, FS_head, FS_cost, FS_trace, FS_rpoint; # initialize n := nops(Network_def); if (n < 1) then printf("Empty network\134n"); return false; end if; result := true; all_done := false; first_seq := true; arc_number := 0; while (not all_done) do; # read next sequence if (first_seq) then seq_data := Network_def[1]; if (nops(seq_data) <> 3) then all_done := true; elif ((seq_data[1] < 1) or (seq_data[2] < 1) or (seq_data[3] < 1) or (seq_data[3] > seq_data[1])) then all_done := true; end if; if (all_done) then result := false; printf("Invalid data: %s\134n", src); printf("Possibly invalid NodeCount, ArcCount, SourceNode\134n"); else NodeCount := seq_data[1]; ArcCount := seq_data[2]; SourceNode := seq_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_seq := false; end if; else # not first_seq, arc definition: from node, to node, cost if ((arc_number + 2) > n) then all_done := true; # EOF, out of arc definitions break; end if; arc_number := arc_number + 1; if (arc_number > ArcCount) then printf("Invalid data: too many arc definitions, %d > %d\134n", arc_number, ArcCount); all_done := true; result := false; else seq_data := Network_def[arc_number+1]; # add 1 because 1st is node count if (nops(seq_data) <> 3) then all_done := true; elif ((seq_data[1] < 1) or (seq_data[1] > NodeCount) or (seq_data[2] < 1) or (seq_data[2] > NodeCount) or (seq_data[3] < 0)) then all_done := true; end if; if (all_done) then result := false; printf("Invalid arc definition: %s\134n", s); printf("Possibly invalid node number or cost\134n"); else raw_tail[arc_number] := seq_data[1]; raw_head[arc_number] := seq_data[2]; raw_cost[arc_number] := seq_data[3]; 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\134n", 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: # loadNetwork # Routine: ShowArcs (internal debugging routine) # Abstract: Display Arcs in network, # traverses 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:\134n\134n"); for node_num to NodeCount do; printf ("From %d:\134n", node_num); for arc_num from FS_point[node_num] to (FS_point[node_num+1] - 1) do; printf("%d. %d - %d\134n", arc_num, FS_tail[arc_num], FS_head[arc_num]); end; end; printf("\134nBackward arcs:\134n\134n"); for node_num to NodeCount do; printf("To %d:\134n", node_num); for arc_num from FS_rpoint[node_num] to (FS_rpoint[node_num+1]-1) do; printf("%d. %d - %d\134n", arc_num, FS_tail[FS_trace[arc_num]], FS_head[FS_trace[arc_num]]); end; end; # all done return true; end proc: # ShowArcs end module: # Dijkstras_Shortest_Path with(Dijkstras_Shortest_Path);

NyNJNERpamtzdHJhc19BbGdvcml0aG1HNiI=