Page 314, Exercise 18

AllCosts fails miserably with the graph of Figure 6.35.  On my computer, AllCosts produced the following results:

ä      0        1       2         3     4        5        6


0   -32767   -32765  -32763   -32767  -32767  -32767  -32767
1        0   -32767  -32766   -32768  -32768  -32768  -32768
2   -32767   -32767  -32766   -32768  -32768  -32768  -32768
3   -32767   -32767  -32768     -348    -354    -390    -606
4   -32768   -32767  -32766     -354    -360    -396    -612
5   -32767   -32767  -32766     -390    -396    -432    -648
6   -32767   -32767  -32766     -606    -612    -648    -864

As you can see, these results are quite interesting.  The negative numbers arise from the arithmetic overflow formed when a path containing MAX_INT is added to any other path.  Since AllCosts does not test the two paths before it adds them, if one of the paths is MaxInt and the other path is anything but a zero, a new
negative path is created.  The graph of Figure 6.35 has many non-existent paths which  corrupt the entire table.  This is in stark contrast to the ShortestPath algorithm which very selectively chooses the path that has the lowest cost. This strategy isolates  a path's ability to corrupt other paths.