最短路问题是网络理论中寻找图中两节点间路径总权值最小的经典问题，权值类型包括距离、时间和成本等，广泛应用于管路铺设、线路安装、厂区布局和设备更新等领域 。其核心算法包括Dijkstra算法（适用于无负权图）、Bellman-Ford算法（解决含负权路径）、Floyd-Warshall算法（计算全局最短路径）以及广度优先搜索（BFS）等 ，清华大学段然团队提出的新算法突破了Dijkstra算法的排序障碍，实现了更快的单源最短路径求解 。
该问题研究始于20世纪50年代，1959年荷兰计算机专家E.W.Dijkstra提出首个赋权图有效算法 。后续发展出Ford算法解决含负权问题，Floyd-Warshall算法改进后能高效计算所有顶点对间最短路 ，SPFA算法通过队列优化将Bellman-Ford算法时间复杂度降至O(k|E|) 。段然团队融合Dijkstra与Bellman-Ford算法，通过递归缩小前沿规模进一步优化运行效率 。
想要了解更多“最短路问题”的信息，请点击：最短路问题百科
