N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。...由列表可知,该字串的3-最短路径结果集合为{5,5,6,6,7}。
当然,在实际情况中,权值不可能都设为1的,否则随着字串长度n和最短路径N的增大,长度相同的路径数将会急剧增加。...然后推广到N-最短路,N-最短路中PreNode有N个,分别对应n-最短路时候的PreNode,就这么简单。...image.png
假定看到这里,算法已经计算出了正确的PreNode队列,下面讨论如何从PreNode中找出N最短路径的确切途经节点集合。...我们得到了3条最短路径,分别是:
0, 1, 3, 6,
0, 1, 2, 3, 6,
0, 1, 2, 4, 5, 6,
推广到N-最短路
N-最短路中PreNode有N个,分别对应n-最短路时候的