单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。 一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。 假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,…

2013年9月30日 0条评论 13点热度 阅读全文

Trie 树, 又称字典树,单词查找树。它来源于retrieval(检索)中取中间四个字符构成(读音同try)。用于存储大量的字符串以便支持快速模式匹配。主要应用在信息检索领域。   Trie 有三种结构: 标准trie (standard trie)、压缩trie、后缀trie(suffix trie) 。 最后一种将在《字符串处理4:后缀树》中详细讲,这里只将前两种。     1. 标准Trie (standard trie)   标准&nb…

2013年9月23日 0条评论 9点热度 阅读全文