标签归档:SPFA

图—最短路径 Dijkstra, SPFA, Floyd

最短路径一看到最,职业病一般的就会想到用动态规划来做。。。至少事实证明的确存在动态规划的解法,但就像上一篇文章中分析的那样,这是一个具有最优子结构的问题,所以我们可以用优雅的贪心算法来解决。

这里我们用来做测试的图如下图所示,还是相当给力了

最短路径

最短路径要解决的实际问题,其实通过名字[……]阅读全文