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)


100 NV=0: REM NUMBER OF VERTICES
110 READ N$:IF N$<>"" THEN NV=NV+1:GOTO 110
120 NE=0: REM NUMBER OF EDGES
130 READ N1:IF N1 >= 0 THEN READ N2,W:NE=NE+1:GOTO 130
140 DIM VN$(NV-1),VD(NV-1,2): REM VERTEX NAMES AND DATA
150 DIM ED(NE-1,2): REM EDGE DATA
160 RESTORE
170 FOR I=0 TO NV-1
180 : READ VN$(I):  REM VERTEX NAME
190 : VD(I,0) = -1: REM DISTANCE = INFINITY
200 : VD(I,1) = 0:  REM NOT YET VISITED
210 : VD(I,2) = -1: REM NO PREV VERTEX YET
220 NEXT I
230 READ N$: REM SKIP SENTINEL
240 FOR I=0 TO NE-1
250 : READ ED(I,0),ED(I,1),ED(I,2): REM EDGE FROM, TO, WEIGHT
260 NEXT I
270 READ N1: REM SKIP SENTINEL
280 READ O: REM ORIGIN VERTEX
290 :
300 REM BEGIN DIJKSTRA'S
310 VD(O,0) = 0: REM DISTANCE TO ORIGIN IS 0
320 CV = 0: REM CURRENT VERTEX IS ORIGIN
330 FOR I=0 TO NE-1
340 : IF ED(I,0)<>CV THEN 390: REM SKIP EDGES NOT FROM CURRENT
350 : N=ED(I,1): REM NEIGHBOR VERTEX
360 : D=VD(CV,0) + ED(I,2): REM TOTAL DISTANCE TO NEIGHBOR THROUGH THIS PATH
370 : REM IF PATH THRU CV < DISTANCE, UPDATE DISTANCE AND PREV VERTEX
380 : IF (VD(N,0)=-1) OR (D<VD(N,0)) THEN VD(N,0) = D:VD(N,2)=CV
390 NEXT I
400 VD(CV,1)=1: REM CURRENT VERTEX HAS BEEN VISITED
410 MV=-1: REM VERTEX WITH MINIMUM DISTANCE SEEN
420 FOR I=0 TO NV-1
430 : IF VD(I,1) THEN 470: REM SKIP VISITED VERTICES
440 : REM IF THIS IS THE SMALLEST DISTANCE SEEN, REMEMBER IT
450 : MD=-1:IF MV > -1 THEN MD=VD(MV,0)
460 : IF ( VD(I,0)<>-1 ) AND ( ( MD=-1 ) OR ( VD(I,0)<MD ) ) THEN MV=I
470 NEXT I
480 IF MD=-1 THEN 510: REM END IF ALL VERTICES VISITED OR AT INFINITY
490 CV=MV
500 GOTO 330
510 PRINT "SHORTEST PATH TO EACH VERTEX FROM "VN$(O)":";CHR$(13)
520 FOR I=0 TO NV-1
530 : IF I=0 THEN 600
540 : PRINT VN$(I)":"VD(I,0)"(";
550 : IF VD(I,0)=-1 THEN 600
560 : N=I
570 : PRINT VN$(N);
580 : IF N<>O THEN PRINT "←";:N=VD(N,2):GOTO 570
590 : PRINT ")"
600 NEXT I
610 DATA A,B,C,D,E,F,""
620 DATA 0,1,7
630 DATA 0,2,9
640 DATA 0,5,14
650 DATA 1,2,10
660 DATA 1,3,15
670 DATA 2,3,11
680 DATA 2,5,2
690 DATA 3,4,6
700 DATA 4,5,9
710 DATA -1
720 DATA 0