This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.

This algorithm is often used in routing and as a subroutine in other graph algorithms.



For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.



For instance

If the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road,   Dijkstra's algorithm can be used to find the shortest route between one city and all other cities.

As a result, the shortest path first is widely used in network routing protocols, most notably:

   IS-IS   (Intermediate System to Intermediate System)   and 
   OSPF   (Open Shortest Path First).


Important note
 
The inputs to Dijkstra's algorithm are a directed and weighted graph consisting of 2 or more nodes, generally represented by:

   an adjacency matrix or list,   and
   a start node. 


A destination node is not specified.

The output is a set of edges depicting the shortest path to each destination node.



An example, starting with

                                         a──►b,  cost=7,   lastNode=a  
                                         a──►c,  cost=9,   lastNode=a 
                                         a──►d,  cost=NA,  lastNode=a
                                         a──►e,  cost=NA,  lastNode=a 
                                         a──►f,  cost=14,  lastNode=a
 
    The lowest cost is    a──►b    so    a──►b    is added to the output. 
 
    There is a connection from   b──►d   so the input is updated to: 
                                         a──►c,  cost=9,   lastNode=a 
                                         a──►d,  cost=22,  lastNode=b 
                                         a──►e,  cost=NA,  lastNode=a 
                                         a──►f,  cost=14,  lastNode=a
 
    The lowest cost is    a──►c    so    a──►c    is added to the output. 
 
    Paths to    d    and    f    are cheaper via    c    so the input is updated to:
                                         a──►d,  cost=20,  lastNode=c 
                                         a──►e,  cost=NA,  lastNode=a 
                                         a──►f,  cost=11,  lastNode=c
 
    The lowest cost is    a──►f    so    c──►f    is added to the output. 
 
    The input is updated to:
                                         a──►d,  cost=20,  lastNode=c 
                                         a──►e,  cost=NA,  lastNode=a
 
    The lowest cost is    a──►d    so    c──►d    is added to the output. 
 
    There is a connection from    d──►e    so the input is updated to:
                                         a──►e,  cost=26,  lastNode=d
 
    Which just leaves adding    d──►e    to the output.
 
    The output should now be:
                                       [ d──►e
                                         c──►d
                                         c──►f
                                         a──►c
                                         a──►b ]   


Task

 Implement a version of Dijkstra's algorithm that outputs a set of edges depicting the shortest path to each reachable node from an origin.
 Run your program with the following directed graph starting at node    a.
 Write a program which interprets the output from the above and use it to output the shortest path from node    a    to nodes    e    and  f. 

 Vertices


 Number 
 Name


 1 
 a


 2 
 b


 3 
 c


 4 
 d


 5 
 e


 6 
 f


 Edges


 Start 
 End 
 Cost


 a 
 b 
 7


 a 
 c 
 9


 a 
 f 
 14


 b 
 c 
 10


 b 
 d 
 15


 c 
 d 
 11


 c 
 f 
 2


 d 
 e 
 6


 e 
 f 
 9



You can use numbers or names to identify vertices in your program.



See also
 Dijkstra's Algorithm vs. A* Search vs. Concurrent Dijkstra's Algorithm (youtube)


# -*- coding: utf-8 -*- #
 
COMMENT REQUIRED BY "prelude_dijkstras_algorithm.a68" CO
  MODE ROUTELEN = ~;
  ROUTELEN route len infinity = max ~;
  PROC route len add = (VERTEX v, ROUTE r)ROUTELEN:
    route len OF v + route len OF r; # or MAX(v,r) #
  MODE VERTEXPAYLOAD = ~;
  PROC dijkstra fix value error = (STRING msg)BOOL:
    (put(stand error, (msg, new line)); FALSE);
#PROVIDES:#
# VERTEX*=~* #
# ROUTE*=~* #
# vertex route*=~* #
END COMMENT
 
MODE VALVERTEX = STRUCT(
    ROUTELEN route len,
    FLEX[0]ROUTE route,
    ROUTE shortest route,
    VERTEXPAYLOAD vertex data
);
 
MODE VERTEX = REF VALVERTEX;
MODE VERTEXYIELD = PROC(VERTEX)VOID; # used to "generate" VERTEX path #
PRIO INIT = 1; # The same PRIOrity as +:= etc #
OP INIT = (VERTEX self, VERTEXPAYLOAD vertex data)VERTEX:
  self := (route len infinity, (), NIL, vertex data);
 
# It may be faster to preallocate "queue", rather then grow a FLEX #
OP +:= = (REF FLEX[]VERTEX in list, VERTEX rhs)REF FLEX[]VERTEX: (
  [UPB in list+1]VERTEX out list;
  out list[:UPB in list] := in list;
  out list[UPB out list] := rhs;
  in list := out list # EXIT #
);
 
MODE VALROUTE = STRUCT(VERTEX from, to, ROUTELEN route len#, ROUTEPAYLOAD#);
MODE ROUTE = REF VALROUTE;
 
OP +:= = (REF FLEX[]ROUTE in list, ROUTE rhs)REF FLEX[]ROUTE: (
  [UPB in list+1]ROUTE out list;
  out list[:UPB in list] := in list;
  out list[UPB out list] := rhs;
  in list := out list # EXIT #
);
 
MODE VERTEXROUTE = UNION(VERTEX, ROUTE);
MODE VERTEXROUTEYIELD = PROC(VERTEXROUTE)VOID;
 
################################################################
# Finally: now the strong typing is in place, the task code... #
################################################################
PROC vertex route gen dijkstra = (
    VERTEX source, target,
    REF[]VALROUTE route list,
    VERTEXROUTEYIELD yield
  )VOID:(
 
# initialise the route len for BOTH directions on each route #
  FOR this TO UPB route list DO
    ROUTE route = route list[this];
    route OF from OF route +:= route;
# assume route lens is the same in both directions, this i.e. NO A-B gradient NOR 1-way streets #
    route OF to OF route +:= (HEAP VALROUTE := (to OF route, from OF route, route len OF route))
  OD;
 
  COMMENT
  Algorithium Performance "about" O(n**2)...
  Optimisations:
       a) bound index in [lwb queue:UPB queue] for search
       b) delay adding vertices until they are actually encountered
  It may be faster to preallocate "queue" vertex list, rather then grow a FLEX
  END COMMENT
 
  PROC vertex gen nearest = (REF FLEX[]VERTEX queue, VERTEXYIELD yield)VOID: (
    INT vertices done := 0, lwb queue := 1;
    ROUTELEN shortest route len done := -route len infinity;
    WHILE vertices done <= UPB queue ANDF shortest route len done NE route len infinity DO
      ROUTELEN shortest route len := route len infinity;
# skip done elements: #
      FOR this FROM lwb queue TO UPB queue DO
        VERTEX this vertex := queue[this];
        IF NOT(shortest route len done < route len OF this vertex) THEN
          lwb queue := this; # remember for next time #
          break
        FI
      OD;
    break:
# find vertex with shortest path attached #
      FOR this FROM lwb queue TO UPB queue DO VERTEX this vertex := queue[this];
        IF shortest route len done < route len OF this vertex ANDF
           route len OF this vertex < shortest route len THEN
           shortest route len := route len OF this vertex FI
      OD;
# update the other vertices with shortest path found #
      FOR this FROM lwb queue TO UPB queue DO VERTEX this vertex := queue[this];
        IF route len OF this vertex = shortest route len THEN
           vertices done +:= 1; yield(this vertex) FI
      OD;
      shortest route len done := shortest route len
    OD
  );
 
  route len OF target := 0;
  FLEX[0]VERTEX queue := target;
 
# FOR VERTEX this vertex IN # vertex gen nearest(queue#) DO (#,
##   (VERTEX this vertex)VOID: (
    FOR this TO UPB route OF this vertex DO ROUTE this route = (route OF this vertex)[this];
 
    # If this vertex has not been encountered before, then add to queue #
      IF route len OF to OF this route = route len infinity THEN queue +:= to OF this route FI;
 
      ROUTELEN route len = route len add(this vertex, this route);
      IF route len < route len OF to OF this route THEN
        route len OF to OF this route := route len;
        shortest route OF to OF this route := this route
      FI
    OD;
 
    IF this vertex IS source THEN done FI
# OD#));
  IF NOT dijkstra fix value error("no path found") THEN stop FI;
 
############################
# Now: generate the result #
############################
  done: ( 
    VERTEX this vertex := source;
    WHILE
      yield(this vertex);
      ROUTE this route = shortest route OF this vertex;
  # WHILE # this route ISNT ROUTE(NIL) DO
      yield(this route);
      this vertex := from OF this route
    OD
  )
);
 
SKIP