我需要做一个算法,找到图中最长的路径。输入将包含两个数字(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中最长的路径吗? 另外,是否有办法记住哪些顶点在最长的路径中?
感谢回复。