今天研究的是图论中的一类基础问题:最短路问题 最短路问题是图论中最基础的问题,在程序设计竞赛试题中也经常出现。最短路是给定两个定点,在以这两个点为起点和终点的路径中,边的权值和最小的路径。如果把权值当作距离,考虑最短距离的话就很容易理解了。智力游戏中的求解最少步数问题也可以说是一种最短路问题。  单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。 一.最短路径的最优子结构性质    该性质描述为:如…

2015年5月13日 0条评论 0点热度 阅读全文