A Maple Package implementing
Dijkstra's Shortest Path Algorithm 

Jay Pedersen
University of Nebraska at Omaha Student
E-mail: jayped007@gmail.com 

Code Version 3, Date 2007-05-31, Maple Version 11

Project: Implement Dijkstras Algorithm for determining shortest paths in a network.
 

References 

Dijkstra's Shortest Path algorithm 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. 

 

Input Format (for Network definition) 

The algorithm takes as input a string containing a network definition.

The assumption is made that nodes are numberd 1:N, where N is the number 

of nodes. 

 

A network definition is a list containing sublists with numeric sequences; which
define the network. 

 

1. The first sublist contains the number of nodes in the network,
   the number of arcs 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. 

 

2. The remaining sublists define the arcs in the network.  Each 

   specifies 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. 

 

Example network definion (4 nodes, 6 arcs, source node is 1): 

net := [ 

[4, 6, 1], 

[1, 2, 1], 

[1, 3, 3], 

[2, 3, 2], 

[3, 2, 4], 

[2, 4, 5], 

[3, 4, 9] 

]; 

Algorithm Code 

 

>

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.\n");            printf("Possible network definition issue, not 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("\nshortest paths from source (from node %d):\n\n", SourceNode);    printf("  To Node   Dist   Prev Node\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;        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\n");        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\n", src);                printf("Possibly invalid NodeCount, ArcCount, SourceNode\n");            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\n",                       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\n", s);                    printf("Possibly invalid node number or cost\n");                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\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: # 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:\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: # ShowArcs end module: # Dijkstras_Shortest_Path with(Dijkstras_Shortest_Path);

 

 

Example Usage 

Usage: The routine Dijkstras_Algorithm is invoked to determine the shortest 

paths from the source node to destination nodes on the network that it is given. 

Syntax: Dijkstras_Algorithm(network[, display_graph]);

Arguments:
Network - list defining the network (see "Input Format" section).
display_graph - true/false, if true => graphically display shortest paths
                                           defaults to false if not specified (=> no graph if not specified) 

shortest paths from source (from node 1):  To Node   Dist   Prev Node        2      1      1        3      3      1        4      6      2

shortest paths from source (from node 1):  To Node   Dist   Prev Node        2      5      1        3      9      1        4     14      6        5      4      1        6      7      5        7      9      5        8     14      1        9     10      5

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.