在加权有向图中解决最短路径问题时，考虑边权重计算时间以及与权重不确定性的关系可以提高性能。通过建立在加权有向图的通用框架上，引入了找到最紧适应最短路径（TASP）的问题，该路径在最优成本的上界上最紧缩，实现了对有界不确定性的最短路径问题的泛化，其中可以用计算成本代替边权重的不确定性。我们提出了一个完整的算法来解决 TASP，并对解决方案的质量进行了保证。实证评估支持这种方法的有效性。

Aug, 2023

研究了在线最短路径问题及其各种监控模型，在加权有向无环图中寻找一条路径以使其对应的边权和尽可能小。提出了一种算法，将累积损失最小化，并介绍了其应用于包交换网络中路由的模拟结果。

Apr, 2007

本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。

Nov, 2014

本论文提出了两种新的算法，用于计算带有实数边权（可能为负数）的有向图的全源最短路径。这两种算法运行时间复杂度为 O (n^2w_d)，可用于空间和时间推理，比 Floyd-Warshall 算法和 Johnson 算法更快，并且具有规划和调度社区的相关性。

Jan, 2014

该篇论文介绍了一种定义在无向图上的全色最短路径问题，它旨在寻找一条最短路径，在路径中每种颜色至少出现一次，假设图中的每个顶点都与一个已知的颜色相关联。该论文证明了这个问题是 NP-hard 的，并提出了用 LP 松弛，模拟退火，蚁群算法和遗传算法等多种启发式方法来解决该问题，并进行了广泛的模拟来进行比较分析。

Jul, 2015

本文研究了一种基于子模集函数的图形切割问题，旨在连接信号处理、机器学习和计算机视觉等应用领域，最后通过算法比较进行了实证研究。

Feb, 2014

对于一个具有未知权重的图，如果我们知道一些节点子集关联的最小 Steiner 树，那么我们能否找到一对节点的最短路径？本文研究了这样一个原型问题，称为具有任务转换的查询 - 决策回归，重点关注最短路径问题和最小 Steiner 树问题。我们提供了关于构建评分模型的可实现假设空间设计的理论洞察，并提出了两个有原则的学习框架。我们的实验研究显示，这样的问题可以在统计显著性的程度上得到较好的解决。

Feb, 2024

本文研究基于 A * 算法和双目标搜索的两种解决方案，解决只有一个约束条件的成本最小路径规划问题，并研究在约束搜索中优先队列的重要性。实验证明，不带打结断的桶队列可以有效提高双目标搜索的算法性能。

Jul, 2022

该研究论文提出一个问题：一次只修改一个顶点，从而将一个最短路径修改为另一个最短路径，其应用于优化网络中的路由算法，数据流管理，以及列车调度等优化问题，并基于图论方法研究该问题的复杂度与算法优化。

Dec, 2021

研究使用密度 p 在 R^d 上按随机方式绘制的 n 个数据点构建的加权或未加权 k 最近邻图的最短路径距离在样本大小趋近于无穷大时的收敛性，证明了对于未加权 k 最近邻图，此距离会收敛到底层空间上的不良距离函数，其性质对机器学习不利。同时，研究了加权 k 最近邻图中最短路径距离的行为。

Jun, 2012