1

我正在通过“计算机算法基础”一书寻找多阶段图问题。

它说：

Algorithm Graph(G,k,n,p)
{
cost[n]=0;
for j=n-1 to 1 step -1 do
{
Let r be a vertex such that<j,r> is an edge of G and c[j,r]+cost[r] is minimum
cost[j]=c[j,r]+cost[r]
}
}

作者说复杂度是 O(|V| + |E|)。|V| 是顶点数，|E| 是边数。

我知道 for 循环针对顶点总数运行，并且内线必须选择一个近边。

我无法理解背后的逻辑

4

1 回答 1

0

为了加深您的理解，请查看 Dijsktra 算法在一个有向图上，每条边也只考虑一次。运行时间为 O(|E| + |V lg V|)。

由于多级图被划分为集合，因此您可以通过集合找到最短路径，因为您知道集合 X 中到目标节点的顶点必须在集合 X-1 之前访问。您还知道同一集合中的顶点之间没有边。简而言之，您知道处理它们的顺序，并且不必像 Dijsktra 中那样每次都考虑所有可能的顶点

于 2012-03-22T07:00:45.587 回答