# Dijkstra in Commodore Basic

Published on 23 October 2023 (Updated: 23 October 2023)

Welcome to the Dijkstra in Commodore Basic page! Here, you'll find the source code for this program as well as a description of how the program works.

## Current Solution

``````10 DIM A(99)
15 REM Graph:
16 REM - G%(i, j, 0) contains vertex index for child node j,  vertex i or
17 REM   negative to indicate no more child nodes
18 REM - G%(i, j, 1) contains weight between vertex i and child node j
20 DIM G%(9, 10, 1)
25 REM Dijkstra result
26 REM - DR(i, 0) contains vertex index of previous node of node i
27 REM - DR(i, 1) contains distance between previous node of node i and node i
28 REM - DR(i, 2) contains 1 if node i visited, 0 otherwise
30 DIM DR(9, 2)
35 REM Get weights
40 GOSUB 2000
50 IF V = 0 OR C >= 0 THEN GOTO 200: REM invalid or not end of input/value
55 REM Get source node
60 GOSUB 1000
70 IF V = 0 OR C >= 0 THEN GOTO 200: REM invalid or not end of input/value
80 NS = NR
85 REM Get destination node
90 GOSUB 1000
100 IF V = 0 OR C >= 0 THEN GOTO 200: REM invalid or not end of input/value
110 ND = NR
115 REM Validate inputs
120 GOSUB 3000
130 IF V = 0 THEN GOTO 200: REM invalid inputs
135 REM Form graph
140 GOSUB 2500
145 REM Perform Dijkstra's algorithm and show result
150 GOSUB 3500
160 S\$ = MID\$(STR\$(DR(ND, 1)), 2)
170 PRINT S\$
180 END
200 PRINT "Usage: please provide three inputs: a serialized matrix, ";
210 PRINT "a source node and a destination node"
220 END
1000 REM Read input value one character at a time since Commodore BASIC
1001 REM has trouble reading line from stdin properly
1002 REM NR = number
1003 REM V = 1 if valid number, 0 otherwise
1004 REM C = -2 if end of input, -1 if end of value,
1005 REM   32 if whitespace, ASCII code of last character otherwise
1006 REM Initialize
1010 NR = 0
1020 V = 0
1030 S = 1
1035 REM Loop while leading spaces
1040 GOSUB 1500
1050 IF C = 43 OR C = 45 THEN GOTO 1100: REM + or -
1060 IF C >= 48 AND C <= 57 THEN GOTO 1150: REM 0 to 9
1070 IF C = 32 THEN GOTO 1040: REM whitespace
1080 RETURN: REM other character
1085 REM Loop while sign
1090 GOSUB 1500
1100 IF C = 43 THEN GOTO 1090: REM +
1110 IF C >= 48 AND C <= 57 THEN GOTO 1150: REM 0 to 9
1120 IF C <> 45 THEN RETURN: REM not -
1130 S = -S
1140 GOTO 1090
1145 REM Set valid flag
1150 V = 1
1155 REM Loop while digits
1160 NR = (ABS(NR) * 10 + C - 48) * S
1170 GOSUB 1500
1180 IF C >= 48 AND C <= 57 THEN GOTO 1160: REM 0 to 9
1185 REM Loop while trailing spaces
1190 IF C < 0 OR C <> 32 THEN RETURN: REM end character or not whitespace
1200 GOSUB 1500
1210 GOTO 1180
1500 REM Get input character
1501 REM A\$ = input character
1502 REM C = One of the following:
1502 REM - -1 if end of value
1503 REM - -2 if end of input
1504 REM - 32 if whitespace
1505 REM - ASCII code otherwise
1510 GET A\$
1520 C = ASC(A\$)
1530 IF C = 13 THEN C = -1
1540 IF C = 255 THEN C = -2
1550 IF C = 9 OR C = 10 THEN C = 32
1560 RETURN
2001 REM A contains array value
2002 REM NA contains length of array
2003 REM V = 1 if valid number, 0 otherwise
2004 REM C = -2 if end of input, -1 if end of value,
2005 REM   32 if whitespace, ASCII code of last character otherwise
2006 REM Initialize
2010 NA = 0
2020 GOSUB 1000: REM Read input value
2030 IF V = 0 THEN RETURN: REM invalid
2040 A(NA) = NR
2050 NA = NA + 1
2060 IF C < 0 THEN RETURN: REM end of input or value
2070 IF C = 44 THEN GOTO 2020: REM comma, get next value
2080 V = 0
2090 RETURN
2500 REM Form graph
2501 REM Inputs:
2502 REM - A contains weights
2504 REM - NV contains number of vertices
2505 REM Output: G% contains graph
2510 K = -1
2520 FOR I = 0 TO NV - 1
2530     N = -1
2540     FOR J = 0 TO NV - 1
2550         K = K + 1
2560         IF A(K) <= 0 THEN GOTO 2600
2570         N = N + 1
2580         G%(I, N, 0) = J
2590         G%(I, N, 1) = A(K)
2600     NEXT J
2610     G%(I, N + 1, 0) = -1: REM End of child nodes
2620     G%(I, N + 1, 1) = 0
2630 NEXT I
2640 RETURN
3000 REM Validate inputs
3001 REM Inputs:
3002 REM - A contains weights
3003 REM - NA contains number of weights
3004 REM - ND contains destination node
3005 REM - NS contains source node
3005 REM Outputs:
3006 REM - V is 1 if valid, 0 otherwise
3007 REM - NV contains the number of vertices
3010 V = 0: REM assume invalid
3020 REM Verify number of weights is a square
3030 NV = INT(SQR(NA) + 0.5)
3040 IF NA <> (NV * NV) THEN GOTO 3160
3055 REM Verify weights greater than zero, and at least one non-zero weight
3060 NZ = 0
3070 I = -1
3080 I = I + 1
3090 IF I >= NV THEN GOTO 3130
3100 IF A(I) < 0 THEN GOTO 3160
3110 IF A(I) <> 0 THEN NZ = 1: REM Non-zero weight found
3120 GOTO 3080
3130 IF NZ = 0 THEN GOTO 3160
3135 REM Verify source and destination node
3140 IF NS < 0 OR NS >= NV OR ND < 0 OR ND >= NV THEN GOTO 3160
3150 V = 1
3160 RETURN
3500 REM Dijkstra's algorithm
3501 REM Source:
3502 REM https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode
3503 REM Inputs:
3504 REM - G% contains graph
3505 REM - NV contains number of vertices
3506 REM - NS contains source node
3507 REM Output: DR contains Dijkstra result
3510 REM Initialize distances to infinite and previous vertices to undefined
3511 REM Set source vertex distance to 0
3512 REM Indicate all nodes unvisited
3520 FOR I = 0 TO NV - 1
3530     DR(I, 0) = -1
3540     DR(I, 1) = 1.70141183E38: REM Infinity
3550     DR(I, 2) = 0
3560 NEXT I
3570 DR(NS, 1) = 0
3575 REM While any unvisited nodes
3580 FOR I = 0 TO NV - 1
3585     REM Pick a vertex u with minimum distance from unvisited nodes
3590     MD = 1.70141183E38: REM Infinity
3600     U = -1
3610     FOR J = 0 TO NV - 1
3620         IF DR(J, 2) <> 0 OR DR(J, 1) >= MD THEN GOTO 3650
3630         MD = DR(J, 1)
3640         U = J
3650     NEXT J
3655     REM Indicate vertex u visited
3660     DR(U, 2) = 1
3665     REM For each unvisited neighbor v of vertex u
3670     J = -1
3680     J = J + 1
3690     V = G%(U, J, 0)
3700     W = G%(U, J, 1)
3710     IF V < 0 THEN GOTO 3780
3720     IF DR(V, 2) <> 0 THEN GOTO 3680
3725     REM Get trial distance
3730     TD = DR(U, 1) + W
3735     REM If trial distance is smaller than distance v, update distance to
3736     REM v and previous vertex of v
3740     IF TD >= DR(V, 1) THEN GOTO 3680
3750     DR(V, 0) = U
3760     DR(V, 1) = TD
3770     GOTO 3680
3780 NEXT I
3790 RETURN

``````

Dijkstra in Commodore Basic was written by:

• rzuckerm

If you see anything you'd like to change or update, please consider contributing.

## How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

## How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.