$title Dijkstra Algorithm (1959) for finding the shortest path in a network

* Slightly modified example from Wikipaedia on Dijkstra algorithm
* see http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.

Set
        Node                /1*6/
;

alias (node,tnode, anode,aanode, origin, destination);

table t(node,anode) 'Time costs on arcs'
     1    2    3   4   5   6
1    0    7    9   0   0   14
2    0    0   10  15   0   0
3    0    0    0  11   0   2
4    0    0    0   0   6   0
5    0    0    0   0   0   9
6    0    0    0   0   0   0;

* Make the matrix symmetric
t(node,anode)$(ord(anode) LT ord(node) ) = t(anode,node);
* Change one arc time to get different routes if going the other way around
t("6","3")                               = 0;

parameter
        previous(origin, destination, node)   'Keep track of previous nodes'
;
set
        od(origin,destination) 'Destination matrix';

* Set some origin-destination pairs
od("1","5") = YES;
od("5","1") = YES;
od("5","3") = YES;

set
        arc(node,anode) 'Arcs'  ;

arc(node,anode)$t(node,anode) =YES;


* Start of the code for the Dijkstra algorithm

parameter
        label(node)      'Labeling of every node',
        counter          'Counter for loops',
        nonvisited(node) 'non visited nodes',
        actual(node)     'node analyzed',
        test             'test for finding the next node'
        templabel(node)  'labels active in the loop';

set
        sequence(node)            'Sequence of nodes to be checked',
        predecessor(node,anode)   'Predecessor as set';

loop(od(origin,destination),

* Initializiation
        
* Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
label(node)         = INF;
label(origin)       = 0;

* Mark all nodes as unnonvisited. Set initial node as current.
nonvisited(node)    = 1;
nonvisited(origin)  = 0;
actual(node)        = 0;
actual(origin)      = 1;

* For current node, consider all its unvisited neighbours and calculate their distance (from the initial node).
* If this distance is less than the previously recorded distance (infinity in the beginning, * zero for the
* initial node), overwrite the distance.

while(sum(node, nonvisited(node)),
        templabel(node) = INF;
        loop((node,anode)$( actual(node) and arc(node,anode) ),
                if(sum(aanode$actual(aanode),label(aanode))
                        + sum(aanode$actual(aanode),t(aanode,anode)) < label(anode),
                nonvisited(anode) = 1;
                previous(origin,destination,anode) = ord(node)$actual(node);
                label(anode)$(not actual(anode)) = sum(aanode$actual(aanode),label(aanode))
                        + sum(aanode$actual(aanode),t(aanode,anode)));
                templabel(anode)$label(anode) = label(anode);
        );
nonvisited(node)$actual(node)           = 0;
actual(node)                            = 0;
test                                    = smin(anode$nonvisited(anode), templabel(anode));
actual(node)$(templabel(node) EQ test)  = 1;
);
);

set
        i         'Set used for writing down the route taken (minimal total nodes)'   /1*6/,
        nodeextra(node)    'Dynamic set for looping over path nodes';

parameter
        aux       'Auxiliary parameter for storing previous node',
        path      'Path taken for every od-pair',
        temp      'Temporary parameter for storing previous node'
;

counter= card(node);

loop(od(origin, destination),
        aux = ord(destination);
        counter = card(node);
        while(counter gt 0,
                nodeextra(node)$(ord(node) eq aux)  = YES;
                path(origin,destination,i)$(ord(i) eq counter) = aux;
                temp = aux;
                loop(nodeextra,
                    aux = previous(origin, destination,nodeextra);
                );
         nodeextra(node)$(ord(node) EQ temp) = NO;
         counter = counter - 1;
        );
);

display path;