小编car*_*eat的帖子

给定一个马尔可夫模型，它有一个名为 的开始状态S和一个名为的退出状态F，这个模型可以表示为一个有向图，有一些约束：

1. 每条边都有一些权重落在 (0,1] 范围内作为转移概率。

2. 从每个节点出来的边的权重总和为 1。

问题是如何对开始状态和退出状态之间的路径进行排序？或者，更准确地说，如何找出概率最高的路径？

一方面，权重是概率，所以路径越长，乘积越小，所以一种启发式策略是选择较短的路径和较大的权重候选者；但是这个问题可以转化为最短路径问题还是使用一些定制的维特比算法或一些DP算法来解决？