仅展示图的最短路径结构时，如何判断两点间最短路径是否可确定？

当仅掌握图的最短路径结构时，判断两个节点u、v间最短路径是否确定，核心是看是否存在多条不同路径，在满足最短路径结构约束的前提下，总权重都能等于u到v的最短距离d(u,v)。具体可按以下步骤分析：

• 明确最短路径结构的边界
  首先区分两类边：属于最短路径结构的边（至少在一条最短路径上的边），以及非最短路径结构的边（不在任何最短路径上的边）。对于非最短路径结构的边(x,y)，其权重必然满足 w(x,y) > d(x,y)（否则这条边会被纳入最短路径结构）。

• 检查同结构内的路径多样性
  如果存在两条完全由最短路径结构内的边组成的不同路径，且它们的总长度等于d(u,v)，那么无论边权重如何设置（只要符合最短路径结构要求），这两条路径都是最短路径，此时u到v的最短路径无法确定。

• 验证跨结构路径的可能性
  对于包含非最短路径结构边的路径P（比如u→...→x→y→...→v），计算其最小可能总长度：d(u,x) + (d(x,y) + ε) + d(y,v)（ε是趋近于0的正数，代表非最短边的最小可能权重）。由于w(x,y) > d(x,y)，这条路径的实际总长度必然大于d(u,v)，不可能成为最短路径，因此这类路径无需纳入判断范围。

• 总结判断准则
  u到v的最短路径能确定的充要条件是：所有由最短路径结构内的边组成的路径中，只有一条的总长度等于d(u,v)。

内容的提问来源于stack exchange，提问作者CSStudent101