戴克斯特拉算法 编辑
戴克斯特拉算法，又译迪杰斯特拉算法，亦可不音译而称为Dijkstra算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法，并于3年后在学术期刊上发表。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。
1
相关
最短路径快速算法，国际上一般认为是带有队列优化的贝尔曼-福特算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中使用堆优化的戴克斯特拉算法效率可能优于SPFA。 SPFA算法首先在1959年由Edward F. Moore作为广度优先搜索的扩展发表，相同算法在1994年由段凡丁重新发现。
最短路径快速算法，国际上一般认为是带有队列优化的贝尔曼-福特算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中使用堆优化的戴克斯特拉算法效率可能优于SPFA。 SPFA算法首先在1959年由Edward F. Moore作为广度优先搜索的扩展发表，相同算法在1994年由段凡丁重新发现。