Q3Comprehension6 Marks31 Aug 2025
Passage
Consider the following condensed version of the "Trains" dataset. There are a total of n stations, with stations being indexed from 0 to n − 1. There are M rows in the table. Each row contains information about a train that connects two stations without any stops in between.
Row r, tells us that train t departs from station i and arrives at station j after covering a distance of d kilometers without stopping at any intermediate station. Therefore, each train t will occupy multiple rows in this table.
This scenario is modeled as a graph and is represented by a matrix A. Each node in the graph corresponds to a station. Assume that the value of n is already given to you. Consider the following pseudocode.
]
```
S = {}
while(Table 1 has more rows){
Read the first row X in Table 1
S[X.SeqNo] = {}
S[X.SeqNo]["train"] = X.Train
S[X.SeqNo]["depart"] = X.Departure
S[X.SeqNo]["arrive"] = X.Arrival
S[X.SeqNo]["dist"] = X.Distance
Move X to Table 2
}
A = createMatrix(n, n)
foreach r in rows(A){
foreach c in columns(A){
A[r][c] = {}
}
}
foreach x in keys(S){
r = S[x]["depart"]
c = S[x]["arrive"]
t = S[x]["train"]
d = S[x]["dist"]
A[r][c][t] = d
}
```
ijMin is a procedure that accepts a pair of stations (i, j), and the matrix A as input. It returns a train which goes from i to j by covering the least distance, without stopping at any intermediate station. If there is no train connecting these two stations, the procedure returns -1. The pseudocode may have mistakes. Identify all of them (if any).
```
Procedure ijMin(i, j, A)
if(length(keys(A[i][j])) == 0){
return(-1)
}
train = first(keys(A[i][j]))
min = A[i][j][train]
foreach k in keys(A[i][j]){
dist = A[i][j][k]
if(dist > min){
min = dist
train = k
}
}
return(train)
End ijMin
```