贝尔福德算法用于单个顶点

Question

贝尔福德算法用于单个顶点

4

我需要做一个算法，找到图中最长的路径。输入将包含两个数字(N,M)，表示矩阵的大小，以及N*M个数字，它们表示每个顶点的值。我必须从第一个顶点到最后一个顶点找到最长的路径，并且只能向下或向右移动。例如，输入如下：

输出结果为

最长的路径按顺序包括这些顶点：1,3,2,4,3,2,2,2

我使用了Bellman-Ford算法，因为我把每个顶点的值改成了负数。但是对于大量顶点（1000x1000），该算法速度太慢了。有没有办法将此算法更改为仅查找两个顶点之间的最长路径（第一个和最后一个），而不是第一个顶点和每个其他顶点之间的路径？以下是我的代码：

# include <stdio.h>
# include <stdlib.h>


typedef struct {
    int source;
    int dest;
    int weight;
} Edge;

void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
{
    int *distance = malloc(nodecount * sizeof *distance);
    int i, j;

    distance[source] = -1;

    for (i=0; i < nodecount; ++i) {
        for (j=0; j < edgecount; ++j) {
            if (distance[edges[j].source] < 0) {
                int new_distance = distance[edges[j].source] + edges[j].weight;
                if (new_distance < distance[edges[j].dest])
                  distance[edges[j].dest] = new_distance;
            }
        }
    }
    printf("%d\n",-distance[nodecount-1]-1);
    free(distance);
    return;
}

int main(void)
{
    Edge *edges;
    edges = malloc(2000000*sizeof(Edge));
    int n,m,i,k,chodbapomoc,q = 0,p = 0,pamat;
    scanf("%d %d",&n,&m);
    for(i = 0; i < n*m;i++){    //this is transformation of input to edges 
       if(i != n*m-1)           //list, so i can go only down or right 
           scanf("%d",&chodbapomoc);
       if(p%m != m-1 && p != 0){
          edges[q].source = p;
          edges[q].dest = p+1;
          edges[q++].weight = -chodbapomoc;
       }
       else if(i == 0){
          k = chodbapomoc;
          scanf("%d",&chodbapomoc);
          edges[q].source = p;
          edges[q].dest = p+1;
          edges[q++].weight = -chodbapomoc-k;
       }
       if(p > m-1 && p != m){
          edges[q].source = p-m;
          edges[q].dest = p;
          edges[q++].weight = -pamat;
       }
       else if(i == m-1){
          edges[q].source = 0;
          edges[q].dest = m;
          edges[q++].weight = -chodbapomoc-k;
       }
       pamat = chodbapomoc;
       p++;
    }
    BellmanFord(edges, q, n*m, 0);
    return 0;
}

还有其他比这个更快的选项来查找DAG中最长的路径吗？另外，是否有办法记住哪些顶点在最长的路径中？

感谢回复。

- Jozef Bugoš

Floyd Warshall 处理节点之间的负距离。 - higuaro

如果我可以向左移动，你如何将输入转换为这些边缘？会发生什么变化？ - user3693423

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- francis · Accepted Answer

有一种算法改进是可能的：在您的情况下，复杂度可以为O（N），其中N是图像上的点数。

Bellman-Ford算法旨在处理任何加权有向图。在最坏的情况下，其复杂度为O（mn），其中n是节点数，m是边数。

请注意，您的有向图是无环的：图中没有定向循环。从任何一个点，都有“未来点”（您将在未来访问它们）和“过去点”（您可能来自那里）。这个属性被Kahn算法用于执行拓扑排序。最后，在这样的有向图中的最短路径算法依赖于拓扑排序，并且总复杂度为O（n+m）！

由于您正在处理一个数组，并且只允许从上到下和从左到右的移动，因此很容易找到拓扑排序。只需按顺序逐行访问，从左到右更新最大距离即可！在程序结束时，图像将填充源点到各个点的最大距离。有四种不同的情况：

i==0 && j==0：这是源点。它的最大距离等于它的权重。
i==0 && j!=0：这是第一行的一个点。到达此处的唯一方法是向左走。因此，它的最大距离是从该行开头到此处的权重之和。
i!=0 && j==0：这是第一列的一个点。到达此处的唯一方法是向下走。因此，它的最大距离是从该列开头到此处的权重之和。
i!=0 && j!=0：一般情况。注意，点(i-1,j)和(i,j-1)已经存储了来自源点的最大距离。到点(i,j)的最大距离是这两个距离中的较大值加上点(i,j)的权重。

最终数组存储了从源点出发的最大距离。另一个数组存储路径信息（最大值来自哪里？）。

第一行：

1 3 8 9 11    s l l l l

第二行：

1 3 8 9  11    s l l l  l
4 6 9 11 12    u l u lu lu

第三行：

1 3  8  9  11    s l l l  l
4 6  9  11 12    u l u lu lu
5 10 13 15 16    u u l l  l

最后一行：

1 3  8  9  11    s l l l  l
4 6  9  11 12    u l u lu lu
5 10 13 15 16    u u l l  l
8 11 15 17 19    u u u lu l

感谢右侧的数组，可以轻松地检索到2条最长路径。该数组仅被读取一次：这个技巧应该会将计算时间减少几个数量级，并且仍然为您提供精确的解决方案！

如果速度仍然太慢，而近似解足以满足需求，请查看simulated annealing。要探索的空间将是路径，例如DDRRRDR，其中有n-1D（向下）和m-1R（向右）。能量将是-distance(DDRRRDR)，一个小修改将交换一个D和一个R。

这是一个精确解决方案（非退火）的示例代码，可以通过gcc main.c -o main -Wall进行编译。编辑：现在它还打印出最大长度的路径之一。

# include <stdio.h>
# include <stdlib.h>



typedef enum {S,L,U,LU} Direction;


int main(void)
{
    FILE * pFile;
    int n=1,m=1,i,j;
    int* image;
    pFile = fopen ("image.txt","r");
    if (pFile!=NULL)
    {
        if(fscanf(pFile,"%d%d",&n,&m)!=2){printf("read failed\n");exit(1);}
        image=malloc(n*m*sizeof(int));
        if(image==NULL){printf("malloc failed\n");exit(1);}
        for(i=0;i<n*m;i++){
            if(fscanf(pFile,"%d",&image[i])!=1){printf("read failed %d\n",i);exit(1);}
        }
        fclose (pFile);
    }else{printf("file open failed\n");exit(1);}

    Direction* directions=malloc(n*m*sizeof(Direction));

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            //getting the direction of max
            if(i==0 && j==0){
                directions[i*m+j]=S;
            }
            if(j==0 && i>0){
                directions[i*m+j]=U;
            }
            if(j>0 && i==0){
                directions[i*m+j]=L;
            }
            if(j>0 && i>0){
                if(image[i*m+(j-1)]>image[(i-1)*m+j]){
                    directions[i*m+j]=L;
                }else{
                    if(image[i*m+(j-1)]<image[(i-1)*m+j]){
                        directions[i*m+j]=U;
                    }else{
                        directions[i*m+j]=LU;
                    }
                }
            }
            //setting the new value of image[i*m+j]
            if(directions[i*m+j]==L){
                image[i*m+j]+=image[i*m+j-1];
            }else{
                if(directions[i*m+j]==U || directions[i*m+j]==LU){
                    image[i*m+j]+=image[(i-1)*m+j];
                }
            }

        }
    }

    printf("max distance is %d\n",image[n*m-1]);

            printf("A path from the end is\n");
    char path[n+m-1];
    path[n+m-2]='\0';
    int cnt=n+m-3;
    i=n-1;
    j=m-1;
    printf("(%d %d)\n",i,j);
    while(i!=0 || j!=0){
        if(directions[i*m+j]==LU){printf("many possible max path. going left\n");}
        if(directions[i*m+j]==U){
            printf("D ");
            path[cnt]='D';
            i--;
        }else{
            printf("R ");
            path[cnt]='R';
            j--;
        }
        cnt--;
        printf("(%d %d)\n",i,j);
    }

    printf("A max path is %s\n",path);
    free(directions);
    free(image);


    return 0;
}

图像存储在名为image.txt的文件中，其外观如下：

A. B. Khan，大型网络的拓扑排序，ACM通讯，第5卷第11期，1962年11月，558-562页，doi:10.1145/368996.369025