对于 (u, v) ∈ E ，有一个有向图 G = [V ; E] ，边权重为 w(u, v) .
(u, v) ∈ E
G = [V ; E]
w(u, v)
假设 {d[v], π[v]}; v ∈ V 和声明的值
{d[v], π[v]}; v ∈ V
这些是最短路径的长度和前一个节点的长度
它为 v ∈ V ，我怎么能验证这个语句是真还是假，不能从头开始解决整个最短路径问题？这是我遇到的一个问题，我头脑中的想法不多 .
v ∈ V
问题有点不清楚，但澄清一下：
图表中有一个节点 s ，每个顶点都有一个节点 v ：
s
v
for v != s ， pi[v] 旨在成为与 v 相邻的节点，该节点位于从 v 到 s 的最短路径上 .
v != s
pi[v]
d[v] 用于存储从 v 到 s 的最短距离 .
d[v]
问题是，鉴于 pi ， d ，它们合法地包含后沿和最小距离 .
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）时间内运行 .
1 回答
问题有点不清楚，但澄清一下：
图表中有一个节点
s，每个顶点都有一个节点v：for
v != s，pi[v]旨在成为与v相邻的节点，该节点位于从v到s的最短路径上 .d[v]用于存储从v到s的最短距离 .问题是，鉴于
pi，d，它们合法地包含后沿和最小距离 .一个容易实现的条件验证了这一点如下：
此检查在O（V E）时间内运行 .