小编cod*_*rAJ的帖子

据说DFS不能用于在未加权图中找到最短路径。我已经阅读了多篇文章和博客，但并不满意，因为在 DFS 中稍作修改就可以使它成为可能。

我想如果我们这样使用Modified DFS，那么我们可以找到离源头的最短距离。

1. 初始化一个到根的距离数组，无穷大，根到自身的距离为 0。
2. 在遍历时，我们会跟踪 no。的边缘。在前进时增加编号。边缘和同时回溯减少数。的边缘。并且每次检查 if(dist(v) > dist(u) + 1 ) 然后 dist(v) = dist(u) + 1。

通过这种方式，我们可以使用 DFS 找到距根的最短距离。通过这种方式，我们可以通过 Dijkstra 在 O(V+E) 而不是 O(ElogV) 中找到它。

如果我在某个时候错了。请告诉我。

我刚刚开始学习新算法，但是当我在极客上阅读极客的Bellman Ford算法时，就陷入了困境：-http: //www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

那里写着-

该算法以自下而上的方式计算最短路径。它首先为路径中最多具有一个边缘的最短路径计算最短距离。然后，它计算最多具有2条边的最短路径，依此类推。

在外循环的第i次迭代之后，将计算最多i个边的最短路径。可以有最大| V |。–在任何简单路径中都有1条边，这就是为什么外循环运行| v |的原因 – 1次。这个想法是，假设不存在负权重循环，如果我们计算出最多具有i个边缘的最短路径，那么对所有边缘进行的迭代将确保给出最多具有（i + 1）个边缘的最短路径。

让我们通过下面的示例图了解算法。图像是从此来源获取的。

假设给定的源顶点为0。将所有距离初始化为无限，除了到源本身的距离。图中的顶点总数为5，因此所有边必须处理4次。

在下面的示例中，如果边的顺序为-（AB），（BE），（ED），（DC），（AC），（BC），（DB），（BD），则仅一次迭代将计算最短甚至具有2-3条边的路径，这与“首先为路径中最多具有一条边缘的最短路径计算最短距离。然后，它计算出具有最多2条边缘的最短路径，以此类推”相反在外循环的第ith次迭代之后，计算出最多具有i条边的最短路径“因此，在更改边的顺序时，该语句将被证明是错误的。

让我们通过下面的示例图了解算法。图像是从此来源获取的。

假设给定的源顶点为0。将所有距离初始化为无限，除了到源本身的距离。图中的顶点总数为5，因此所有边必须处理4次。

让所有边缘按以下顺序处理：（B，E），（D，B），（B，D），（A，B），（A，C），（D，C），（B，C） ，（E，D）。第一次处理所有边缘时，我们得到以下距离。第一行显示初始距离。第二行显示处理边缘（B，E），（D，B），（B，D）和（A，B）时的距离。第三行显示处理（A，C）时的距离。第四行显示何时处理（D，C），（B，C）和（E，D）。

第一次迭代保证给出最长为1个边长的所有最短路径。第二次处理所有边缘时，我们得到以下距离（最后一行显示最终值）。

第二次迭代保证给出最长为2个边长的所有最短路径。该算法将所有边缘再处理2次。在第二次迭代后将距离最小化，因此第三次和第四次迭代不会更新距离。

此代码给出了分段错误.在GDB调试时,它给出了这个错误:

"程序收到信号SIGSEGV,分段错误.在_IO_vfscanf_internal中的0x00007ffff7a6dde5(s =,格式=,argptr = argptr @ entry = 0x7fffffffdba8,errp = errp @ entry = 0x0)at vfscanf.c:1902 1902 vfscanf.c:没有这样的文件或目录. "

void  readData()
{
int **arr,m;
scanf("%d",&m);
arr = (int **)malloc(sizeof(int)*m);
    for(int i=0;i<m;i++)
    {
    arr[i] = (int *)malloc(sizeof(int) * 2);
    }
    for(int i=0;i<m;i++)
    {
    printf("..%d ..\n",i); // if m = 20 then running only 12 times
    scanf("%d %d",&arr[i][0],&arr[i][1]);

    }
}

int main()
{
readData();
}

如果m = 20那么,第二个循环只运行12次然后给出分段错误.第一个循环运行20次. 请帮帮我.