Я работаю над проектом, чтобы найти кратчайший путь до 50000 точек в 2d массиве (200 * 250). Чтобы было проще, я только начал с 2 * 2.
Из точек могу выйти N, W, E, S (без получения матрицы)
У меня есть 3 2d массива.
Map [] [] = содержит двоичные значения от 0 до 255
known [] [] = 0 или 1. 1 означает, что он нашел кратчайший путь для точки. в начале все значения равны 0.
Dist [] [] = пункт назначения кратчайшего пути. На старте все значения 9999
У меня есть три функции, одна из которых является dijkstra ().
void dijkstra(){
dist[0][0]=0;
int i,j,counter=0;
while(counter<=9){
if(counter<9){
cout<<"counter: "<<counter<<endl;
}
returnmin2(0,0);
known[x][y]=1;
returnS(x);
returnN(x);
returnE(y);
returnW(y);
if(s!=-1){
if(known[s][y]==0){
cost=sqrt(1+(pow((map[s][y]-map[s-1][y]),2.0)));
cost1=cost+dist[s-1][y];
if(cost1<dist[s][y]){
dist[s][y]=cost1;
path[s][y]=150;
cout<<"Distance: "<<dist[s][y]<<endl;
}
}
}
if(n!=-1){
if(known[n][y]==0){
cost=sqrt(1+(pow((map[n][y]-map[x][y]),2.0)));
cost1=cost+dist[n+1][y];
if(cost1<dist[n][y]){
dist[n][y]=cost1;
path[n][y]=50;
cout<<"Distance: "<<dist[x][y]<<endl;
}
}
}
if(e!=-1){
if(known[x][e]==0){
cost=sqrt(1+(pow((map[x][e]-map[x][e-1]),2.0)));
cost1=cost+dist[x][e-1];
if(cost1<dist[x][e]){
dist[x][e]=cost1;
path[x][e]=100;
cout<<"Distance: "<<dist[x][w]<<endl;
}
}
}
if(w!=-1){
if(known[x][w]==0){
cost=sqrt(1+(pow((map[x][w]-map[x][w+1]),2.0)));
cost1=cost+dist[x][w+1];
float d= dist[x][w+1];
if(cost1<dist[x][w]){
dist[x][w]=cost1;
path[x][w]=200;
cout<<"Distance: "<<dist[x][w]<<endl;
}
}
}
counter++;
}
}
функцияreturnmin
найти наименьшее расстояние, которое неизвестно.
float returnmin2(int i,int j){
float min2,q=0;
for(i;i<3;i++){
for(j;j<3;j++){
float q=dist[i][j];
if((i==0) && (j==0)){
min2=q;
x=i;
y=j;
}
if(q<min2){
min2=q;
x=i;
y=j;
}
}
}
if(known[x][y]==0){
x=x;
y=y;
}
else if(known[x][y]!=0){
if(y<2){
returnmin2(x,y+1);
}
else {
returnmin2(x+1,0);
}
}
}
returnS, N, W, E — это функции, которые говорят, каким путем мы можем идти
int returnS(int v){
if(v!=2){
s=v+1;
}
else{
s=-1;
}
}
По какой-то причине программа перестает работать, когда счетчик достигает 5. Я до сих пор уверен, почему. на старте все работает нормально. но по какой-то причине, когда он достигает пункта 2,2, он пропускает. Пожалуйста, дайте мне знать, если вы хотите, чтобы я включил функцию openfile и main
Задача ещё не решена.
Других решений пока нет …