Initial value and backpointer matrices:
   Value matrix:
 0 18 16 -1 
 *  0  *  * 
 * 20  0  1 
35  *  *  0 
   Backpointer matrix:
 *  1  1  1 
 *  *  *  * 
 *  3  *  3 
 4  *  *  * 

After 1 iteration of the main loop:
   Value matrix:
 0 18 16 -1 
 *  0  *  * 
 * 20  0  1 
35 53 51  0 
   Backpointer matrix:
 *  1  1  1 
 *  *  *  * 
 *  3  *  3 
 4  1  1  * 

After 2 iterations of the main loop:
   Value matrix:
 0 18 16 -1 
 *  0  *  * 
 * 20  0  1 
35 53 51  0 
   Backpointer matrix:
 *  1  1  1 
 *  *  *  * 
 *  3  *  3 
 4  1  1  * 

After 3 iterations of the main loop:
   Value matrix:
 0 18 16 -1 
 *  0  *  * 
 * 20  0  1 
35 53 51  0 
   Backpointer matrix:
 *  1  1  1 
 *  *  *  * 
 *  3  *  3 
 4  1  1  * 

After 4 iterations of the main loop:
   Value matrix:
 0 18 16 -1 
 *  0  *  * 
36 20  0  1 
35 53 51  0 
   Backpointer matrix:
 *  1  1  1 
 *  *  *  * 
 4  3  *  3 
 4  1  1  * 

Shortest path from 1 to 1: 1: cost = 0
Shortest path from 1 to 2: 1 2: cost = 18
Shortest path from 1 to 3: 1 3: cost = 16
Shortest path from 1 to 4: 1 4: cost = -1
Shortest path from 2 to 2: 2: cost = 0
Shortest path from 3 to 1: 3 4 1: cost = 36
Shortest path from 3 to 2: 3 2: cost = 20
Shortest path from 3 to 3: 3: cost = 0
Shortest path from 3 to 4: 3 4: cost = 1
Shortest path from 4 to 1: 4 1: cost = 35
Shortest path from 4 to 2: 4 1 2: cost = 53
Shortest path from 4 to 3: 4 1 3: cost = 51
Shortest path from 4 to 4: 4: cost = 0