c - 一个顶点的 Bellman-ford 算法

Question

我有一个任务要做算法，它会找到图中最长的路径。我将输入两个数字 (N,M)，这意味着矩阵的大小，以及 N*M 数字。它们表示每个顶点的值。我必须找到从第一个顶点到最后一个顶点的最长路径，而且我只能向下或向右移动。所以输入例如:

4 5
1 2 5 1 2
3 2 1 2 1
1 4 3 2 1
3 1 2 2 2

输出是

19    

最长的路径包括这些顶点的顺序: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 中的最长路径？还有，有什么办法可以记住哪些顶点在最大路径上？

谢谢回复

Answer 1

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

Bellman-Ford algorithm旨在处理任何 weighted digraph .它在最坏情况下的复杂度是 O(mn)，其中 n 是节点数，m 是边数。

请注意，您的二合字母是 acyclic :您的图表中没有定向循环。从任何一个点出发，都有“ future 点”(你在未来访问它们)和“过去点”(你可能来自那里)。 Kahn 算法使用此属性来执行 topological sorting .最后，这种有向图中的最短路径算法依赖于拓扑排序，总复杂度为 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-1 D(向下)和 m-1 的路径R(右)。能量将是 -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 中提供，如下所示:

4 5
1 2 5 1 2
3 2 1 2 1
1 4 3 2 1
3 1 2 2 2

一个。 B. 汗，Topological sorting of large networks ACM 通讯第 5 卷第 11 期，1962 年 11 月第 558-562 页 doi:10.1145/368996.369025