🤔 对 Dijkstra's Algorithm 的体会

Dijkstra 算法以前就用到过，但并没有形成深刻的认识。它可以用来求两点之间的最短距离，比如，我们从一个地方到另外一个地方，需要找一条最短的路径，就可以用到此算法。该算法也可以用到分析其他的问题，比如 Currency Exchange Problem，可阅读 Melissa Yan 的讲稿。

不管怎样，这些问题都可以抽象成图的最短路问题，这在数据结构、数学建模和算法导论里面都有描述。对于这样的问题，只要确定起始点 v，Dijkstra 执行完一遍可以得到 v 到其余所有点的最短距离。

凝视着数据结构上的 Dijkstra’s Algorithm 良久，仍然没弄懂其算法流程。最后，在网上查阅一番，发现维基百科上有一个该算法的动态图。照着这个图动手画一画，然后再看算法的关键迭代式，思路就比较清晰了。

dist[i] = min {dist[i], dist[k] +  arc[k][i]}

理解了算法，就想动手实现，于是想用 JavaScript 写。搜一搜，实际上 GitHub 上已经有各种版本的算法实现。想想还是算了，只是由于没懂 Dijkstra 这个算法，要来把它解决了。

对于要查找任意两点之间的距离的情况，建议提前全部计算获得，后面直接根据下标提取，这样效率会比较高。而查找每一对点之间的距离，也可以用 Floyd 算法，它形式上更简单，并且对于全部查找的情况，两者的时间复杂度都是 O(n³)。对于像 2011 年的《交巡警服务平台》这个数学建模题，就能够用得上这两个算法。

至此，就是我看 Dijkstra’s Algorithm 的心得体会，并没有要详述算法的意思。