最優性原理

最優性原理，這個重要原理從概念上講很好理解，它的意思是：如果給定從A到C的最優路線，那麼從最優路線上任意一點B到C的路線Ⅱ必須是由B到C的最優路線。如果路線弧AB+弧BⅡC是到的最優路線，則最優性原理表明：弧BⅡC一定是從到的最優路線。這一點可以用反證法證明。

如果存在另一條路線弧BIC是從到的比弧BⅡC有更小代價的最優路線。那麼沿弧AB+ 弧BIC就比弧AB+ 弧BⅡC有更小代價的最優路線。但是這個結論恰好與路線弧AB+ 弧BⅡC是由到的最優路線(即代價最小)的假設矛盾，這個矛盾說明，沒有比從到沿弧BⅡC的代價更小的路線。也就是說，路線弧AB+ 弧BⅡC是由到的最優路線。