The Specifications of the Input File:

The file we read from will be given in a special form. It is easiest to understand this form form an example. Here is a graph of 12 nodes and 23 edges:

12 23
1 4 7 8 11 14 15 18 21 22 23 24 24
12 8 100
12 9 12
12 11 4
11 7 70
11 8 1
11 10 2
10 7 9
9 5 90
9 6 5
9 8 0
8 4 60
8 5 7
8 7 2
7 4 11
6 2 80
6 3 4
6 5 3
5 1 50
5 2 1
5 4 3
4 1 10
3 2 7
2 1 5

The first entries on row 1 are of the form n m where n denotes the number of nodes and m is the number of edges. The next row of values are read into an array ListArray. The lines after this line contain information in the form of the triple from_node to_node edge_cost. The ListArray starts at the last node, here 12, and goes to the first node, here 1. The line

1 4 7 8 11 14 15 18 21 22 23 24 24

is interpreted to mean that node 12 has its list of edges start on first line below the ListArray line, node 11 has its list of edges start on line 4 after the ListArray line and so forth. Hence we could annotate this ListArray line as follows:

1                           4 
Start of node 12 edge list  start of node 11 edge list
7                           8 
Start of node 10 edge list  start of node 9 edge list                         
11                         14 
Start of node 8 edge list  start of node 7 edge list
15                         18
Start of node 6 edge list  start of node 5 edge list 
21                         22
Start of node 4 edge list  start of node 3 edge list 
23                         
Start of node 2 edge list
24  24
start of node 1 edge list

The last two entries are special as we have no edges going into the first node. So the double m + 1 m + 1 indicates this, where recall the m is the number of edges. We list as many lines as needed for the ListArray. The edges listed for a given node are listed in a certain order. For example,

8 4 60
8 5 7
8 7 2

shows that there are 3 arcs terminate at node 8 which correspond to forward arcs, 4 $\longrightarrow$ 8 with cost 60, 5 $\longrightarrow$ 8 with cost 7, and 7 $\longrightarrow$ 8 with cost 2. Note, these are listed in the increasing order, 4, 5, 7.