Bellman-Ford Algorithm for One Peak

Question

I have a task to make an algorithm that finds the longest path in a graph. I will have two numbers in the input (N,M), which mean the size of the matrix and the number N*M. They mean the value of each vertex. I have to find the longest path from the first peak to the last, and I can only move down or to the right. So input, for example:

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

And conclusion

19    

The longest path includes the following peaks: 1,3,2,4,3,2,2,2

I used the Bellman-Ford algorithm because I changed the value of each vertex to negative. But this algorithm is too small for a large number of winds (1000x1000). Is it possible to change this algorithm to find only the largest path between two vertices (first and last), and not the path between the first and every other vertex? Here is my code:

# 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;
}

Or is there another option, faster than this, to find the longest path in the DAG? And is there a way to remember which versions are on the longest path?

thanks for the answer

Answer 1

There is an algorithmic improvement: in your case, the complexity may be O(N), where Nis the number of points in your image.

- . O(mn), N - node m .

, acyclic: . - " " ( ) " " ( ). . , , 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).

. ( max?).

:

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

Thrid:

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

, . : , - !

, . , DDRRRDR n-1 D () m-1 R (). -distance(DDRRRDR), D R.

( ), gcc main.c -o main -Wall. EDIT: .

# 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

. . , ACM 5 11, 1962 . 558-562 doi: 10.1145/368996.369025