找到有向图的最短路径

Question

有一个有向图G = [V ; E]，边的权值为w(u, v)为(u, v) ∈ E。

假设值{d[v], π[v]}; v ∈ V并声称

，这些都是最短路径的长度和

它v ∈ V前身节点，我怎么能验证，如果这个说法是真的还是假的，做没有从头开始解决整个最短路径问题？这是一个问题，我遇到了我的脑袋没有太多的想法..

Answer 1

的问题是有点不清楚，但澄清：

有一个在你的图形中的节点s，并且对于每个顶点v：

1. 为v != s，pi[v]旨在是相邻v节点这是从v到s的最短路径上。
2. d[v]旨在存储从v到s的最短距离。

问题是验证pi，d，他们合法地包含后缘和最小距离。

用于验证这样的一个容易实施的条件如下：

For each vertex v 
    Either: 
     v = s and d[v] = 0 
    Or: 
    d[pi[v]] = d[v] - 1 
    d[u] >= d[v] - 1 for each u adjacent to v 
    pi[v] is adjacent to v 

此检查运行在O（V + E）的时间。