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)


program dijkstra(output);
 
type
  { We dynamically build the list of vertices from the edge list,
    just to avoid repeating ourselves in the graph input. Vertices are linked
    together via their `next` pointers to form a list of all vertices (sorted by
    name), while the `previous` pointer indicates the previous vertex along the
    shortest path to this one. }
  vertex = record
    name: char;
    visited: boolean;
    distance: integer;
    previous: ^vertex;
    next: ^vertex;
  end;
 
  vptr = ^vertex;
 
  { The graph is specified as an array of these }
  edge_desc = record
    source: char;
    dest: char;
    weight: integer;
  end;
 
const
  { the input graph }
  edges:    array of edge_desc = (
    (source:'a'; dest:'b'; weight:7),
    (source:'a'; dest:'c'; weight:9),
    (source:'a'; dest:'f'; weight:14),
    (source:'b'; dest:'c'; weight:10),
    (source:'b'; dest:'d'; weight:15),
    (source:'c'; dest:'d'; weight:11),
    (source:'c'; dest:'f'; weight:2),
    (source:'d'; dest:'e'; weight:6),
    (source:'e'; dest:'f'; weight:9)
  );
 
  { find the shortest path to all nodes starting from this one }
  origin: char = 'a';
 
var
  head_vertex: vptr = nil;
  curr, next, closest: vptr;
  vtx: vptr;
  dist: integer;
  edge: edge_desc;
  done: boolean = false;
 
{ allocate a new vertex node with the given name and `next` pointer }
function new_vertex(key: char; next: vptr): vptr;
 
  var
    vtx: vptr;
  begin
    new(vtx);
    vtx^.name := key;
    vtx^.visited := false;
    vtx^.distance := maxint;
    vtx^.previous := nil;
    vtx^.next := next;
    new_vertex := vtx;
  end;
 
 
{ look up a vertex by name; create it if needed }
function find_or_make_vertex(key: char): vptr; var
    vtx, prev, found: vptr;
    done: boolean;
 
  begin
 
    found := nil;
    if head_vertex = nil then
      head_vertex := new_vertex(key, nil)
    else if head_vertex^.name > key then
      head_vertex := new_vertex(key, head_vertex);
 
    if head_vertex^.name = key then
      found := head_vertex
    else begin
      prev := head_vertex;
      vtx := head_vertex^.next;
      done := false;
      while not done do
        if vtx = nil then
          done := true
        else if vtx^.name >= key then
          done := true
        else begin
          prev := vtx;
          vtx := vtx^.next
        end;
      if vtx <> nil then
        if vtx^.name = key then
          found := vtx;
      if found = nil then begin
        prev^.next := new_vertex(key, vtx);
        found := prev^.next;
      end
    end;
    find_or_make_vertex := found
  end;
 
{ display the path to a vertex indicated by its `previous` pointer chain }
procedure write_path(vtx: vptr);
  begin
    if vtx <> nil then begin
      if vtx^.previous <> nil then begin
        write_path(vtx^.previous);
        write('→');
      end;
      write(vtx^.name);
    end;
  end;
 
begin
  curr := find_or_make_vertex(origin);
  curr^.distance := 0;
  curr^.previous := nil;
  while not done do begin
    for edge in edges do begin
      if edge.source = curr^.name then begin
        next := find_or_make_vertex(edge.dest);
        dist := curr^.distance + edge.weight;
        if dist < next^.distance then begin
           next^.distance := dist;
           next^.previous := curr;
        end
      end
    end;
    curr^.visited := true;
    closest := nil;
    vtx := head_vertex;
    while vtx <> nil do begin
      if not vtx^.visited then
        if closest = nil then
          closest := vtx
        else if vtx^.distance < closest^.distance then
          closest := vtx;
      vtx := vtx^.next;
    end;
    if closest = nil then
      done := true
    else if closest^.distance = maxint then
      done := true;
    curr := closest;
  end;
  writeln('Shortest path to each vertex from ', origin, ':');
  vtx := head_vertex;
  while vtx <> nil do begin
    write(vtx^.name, ':', vtx^.distance);
    if vtx^.distance > 0 then begin
      write(' (');
      write_path(vtx);
      write(')');
    end;
    writeln();
    vtx := vtx^.next;
  end
end.