求关键路径，这里为啥会报错？

Question

求关键路径，这里为啥会报错？

完整代码：

void KeyPath(AdjGraph* G)
{
    int topsort[MAXV];
    TopSort(G, topsort);
    int ve[MAXV] = { 0 };
    int vl[MAXV];
    int lnode = topsort[0];
    int enode = topsort[G->n - 1];
    int ee = 0;
    int el = 0;
    int i = 0;
    ArcNode* p = NULL;
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            if (ve[p->adjvex] < ve[i] + p->weight)
            {
                ve[p->adjvex] = ve[i] + p->weight;
            }
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)//vl数组的初始化
    {
        //vl[i] = ve[G->n - 1];
        vl[i] = ve[enode];
    }
    for (i = G->n - 2; i >= 0; i++)//n -2
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            //if (ve[i] - p->weight < vl[i])
            if (vl[p->adjvex] - p->weight < vl[i])
            {
                vl[i] = vl[p->adjvex] - p->weight;
            }
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            ee = ve[i];
            //el = vl[i] - p->weight;
            el = vl[p->adjvex] - p->weight;
            if (ee == el)
            {
                printf("%3d%3d%3d", i, p->adjvex, p->weight);
            }
            p = p->nextarc;
        }
    }
}

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：

在你的代码中，第二个 for 循环的条件写成了 i++，应该是 i--。因此，当循环到 i = G->n - 1 时，i++ 会使 i 的值超出数组 vl 的索引范围，导致运行时错误。

更正后的代码如下：

void KeyPath(AdjGraph* G)
{
    int topsort[MAXV];
    TopSort(G, topsort);
    int ve[MAXV] = { 0 };
    int vl[MAXV];
    int lnode = topsort[0];
    int enode = topsort[G->n - 1];
    int ee = 0;
    int el = 0;
    int i = 0;
    ArcNode* p = NULL;
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            if (ve[p->adjvex] < ve[i] + p->weight)
            {
                ve[p->adjvex] = ve[i] + p->weight;
            }
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)//vl数组的初始化
    {
        //vl[i] = ve[G->n - 1];
        vl[i] = ve[enode];
    }
    for (i = G->n - 2; i >= 0; i--)//修正此处的循环条件
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            //if (ve[i] - p->weight < vl[i])
            if (vl[p->adjvex] - p->weight < vl[i])
            {
                vl[i] = vl[p->adjvex] - p->weight;
            }
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            ee = ve[i];
            //el = vl[i] - p->weight;
            el = vl[p->adjvex] - p->weight;
            if (ee == el)
            {
                printf("%3d%3d%3d", i, p->adjvex, p->weight);
            }
            p = p->nextarc;
        }
    }
}

现在，你的代码应该能够正确运行并求得关键路径。

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢