Bellman-ford algorithm for one vertex

Question

I have a task to do algorithm, which will find the longest path in a graph. I will have on the input two numbers (N,M), which mean size of matrix, and N*M numbers. They mean value of each vertex. I must find the longest path from first vertex to last and I can move only down or 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 output is

19    

The longest path includes in order these vertices: 1,3,2,4,3,2,2,2

I have used Bellman-Ford algorithm, because I have changed value of each vertex to negative. But this algorithm is just too slow for big numbers of vetices (1000x1000). Is there any option to change this algorithm to find only largest way between two vertices (first and last), instead of way between 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 other option, faster than this, to find the longest path in DAG? And, is there any way to remember which verices are in the largest path?

Thanks for respond

Answer 1

There is an algorithmic improvement that is possible : in your case, the complexity can be O(N) where N is the number of points on your image.

The Bellman-Ford algorithm is designed to handle any weighted digraph. Its complexity in the worst case is O(mn) where n is the number of node and m the number of edges.

Notice that your digraph is acyclic : there is no oriented cycles in your graph. From any points, there are "future points" (you visit them in the future) and "past points" (you may come from there). This property is used by the Kahn algorithm to perform topological sorting. Finally, the shortest path algorithm in such a digraph relies on a topological ordering and the total complexity is O(n+m) !

Since you are working on an array, and since only top->bottom and left->right movements are allowed, it is easy to find a topological ordering. Just visit the lines one after another, from left to right and update the maximum distance on the way ! At the end of the program, the image is populated with max distances from the source. There are four different cases :

• i==0 && j==0 : this is the source point. Its max distance is equal to its weight.
• i==0 && j!=0 : this is a point in the first line. The only way to get there is to go left. So its max distance is the sum of weights from the beginning of the line.
• i!=0 && j==0 : this is a point in the first column. The only way to get there is to go down. So its max distance is the sum of weights from the beggining of the column.
• i!=0 && j!=0 : the general case. Notice that the points (i-1,j) and (i,j-1) already host the max distances from the source. The max distance to point (i,j) is the largest of these two distances plus the weight of point (i,j).

The final array stores the maximum distance from the source. An additional array stores the path information (where does the max come from ?).

First line :

1 3 8 9 11    s l l l l

Second line :

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

Thrid line :

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

Last line :

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

Thanks to the array on the right, the 2 longest paths can easily be retreived. The array is read only once : this trick should reduce your computational time by a few orders of magnitude and it still provides you with the exact solution !

If it remains too slow and if an approximated solution is enough, take a look at simulated annealing. The space to explore would be paths such as DDRRRDR with n-1 D (down) and m-1 R (right). The energy would be -distance(DDRRRDR) and a minor modification would be swapping one D and one R.

Here is an example code of the exact solution (not annealing), to be compiled by gcc main.c -o main -Wall. EDIT : it also prints one of the path of max length now.

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

The image is provided in file image.txt which looks like :

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

A. B. Khan , Topological sorting of large networks Communications of the ACM Volume 5 Issue 11, Nov. 1962 Pages 558-562 doi:10.1145/368996.369025