包概述
DJK 包提供了一组 API,用于在图中查找从源顶点到目的顶点的一组最短路径。在本包的语境中,“最短路径”指代价最小的路径,其中代价为路径各边权重之和。
DJK 包核心的算法与数据结构基于 Dijkstra 最短路径算法,并加以修改和扩展。在使用本包之前,最好先熟悉 Dijkstra 算法。有许多优秀的参考资料描述了基本的 Dijkstra 算法,包括 1、3 和 4(列于参考资料中)。
API 选择上的取舍会极大地影响使用 DJK 包的代码的性能。某些函数是独立函数,另一些函数则需配合使用:先构建结果缓存,再通过后续调用检索结果。本节旨在就常见用例下如何高效使用 DJK 包给出一些指导。