我有一个要执行算法的任务，该算法将在图中找到最长的路径。我将在输入两个数字上有 (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
我已经使用了贝尔曼福音算法，因为我已经将每个顶点的值更改为负。但是，对于大量的兽医（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("%dn",-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中最长的路径？而且，有什么方法可以记住哪些雕像在最大的路径中？
感谢您的响应
有可能的算法改进是可能的：在您的情况下，复杂性可以是 O(N)，其中 N是图像上的点数。
Bellman-Ford算法旨在处理任何加权挖掘物。在最坏情况下，其复杂性是 O(mn)，其中 n是节点的数量和 m边缘数。
请注意，您的Digraph是无环的：图中没有方向的周期。从任何角度来看，都有"未来"（您将来访问他们）和"过去"（您可能来自那里）。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条最长的路径。数组仅读取一次：此技巧应减少几个数量级的计算时间，并且仍然为您提供精确的解决方案！
如果它保持太慢，并且近似解决方案足够，请查看模拟退火。要探索的空间将是诸如DDRRRDR n-1 D（down）和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 failedn");exit(1);}
image=malloc(n*m*sizeof(int));
if(image==NULL){printf("malloc failedn");exit(1);}
for(i=0;i<n*m;i++){
if(fscanf(pFile,"%d",&image[i])!=1){printf("read failed %dn",i);exit(1);}
}
fclose (pFile);
}else{printf("file open failedn");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 %dn",image[n*m-1]);
printf("A path from the end isn");
char path[n+m-1];
path[n+m-2]=' ';
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 leftn");}
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 %sn",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
a。B. Khan，ACM大型网络通信的拓扑排序第5卷第11期，1962年11月第558-562页doi：10.1145/368996.369025