给定一个无向图g={e，v}，边代价为正。对于所有节点组合，是否有方法确定某个节点v是否不在其非端点的任何最短路径上？
我的想法是，可以通过在每个节点上执行Dijkstra算法的修改形式来完成，除了v，它会标记v是否在解中但我不知道如何修改算法来实现这一点。
最佳答案
假设v是顶点，a和b是相对的起点和终点。
查找从a到b的最短路径长度。
找到从a到v和v到b的最短路径长度。
如果步骤2的和等于步骤1的值，v处于从a到b的潜在最短路径上。
PS:算法的时间复杂度与寻找最短路径相同。
更新：dijkstra从一个节点开始，并将最小距离从该节点传播到其他节点。它会一直这样做，直到到达所有节点（while Q is not empty）如果您对某个特定节点（端点）感兴趣，可以在dijkstra中执行此过程，直到到达该点（即假设t是目标点，则执行（最小）距离传播，直到从u中提取Q。另一方面，在这行u ← vertex in Q with min dist[u]这样u equals t你可以return dist[u]）有关dijkstra和良好的图形说明，请参见this。
关于algorithm - 确定顶点是否在任何最短路径中的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47724898/