Design and Analysis of Algorithms

304 Design and Analysis of Algorithms

Summary

Results of dynfgrph.c

dynfgrph.c: Give name of input data file: test5.dat

12 nodes, 5 stages and 28 edges in the graph

minimum cost = 16.0, the path is:

[1]−{9.0}−>[2]−{2.0}−>[7]−{3.0}−>[10]−{2.0}−>[12].

Give name of input data file: test90.dat

90 nodes, 10 stages and 869 edges in the graph

minimum cost = 95.0, the path is:

[1]−{13.0}−>[9]−{4.0}−>[16]−{17.0}−>[25]−{6.0}−>[41]−{1.0}−>[47]−{8.0}−>

[66]−{4.0}−>[76]−{11.0}−>[87]−{31.0}−>[90].

TYPICAL RESULTS

The Greedy strategy which we discussed in chapter 10 was shown to be limited in its range of

applicability. Dynamic programming is a more widely applicable ...