Pourquoi cette implémentation de Dijkstra (graphique) ne fonctionne pas?

Question

J'ai fait cette mise en œuvre pour ce problème: http://www.spoj.pl/problems/SHOP/

---

#include<iostream> 
#include<stdio.h> 
#include<queue> 
#include<conio.h> 
#include<string.h> 
using namespace std; 

struct node 
{ 
    int x; 
    int y; 
    int time; 
}; 
bool operator <(const node &s,const node &r) 
{ 
    if(s.time>r.time) 
    return true; 
    else return false; 
} 
node beg,src,dest,tempa; 
int b,a,temp; 
int map[25][25]; 
bool vis[25][25]; 
int X[]={1,0,-1,0}; 
int Y[]={0,1,0,-1}; 


int djs_bfs(node src,node dest) 
{ 
    int result=0; 
    priority_queue<node>pq; 
    pq.push(src); 
    while(!pq.empty()) 
    { 
     node top = pq.top(); 
     pq.pop(); 
     if(top.x==dest.x && top.y==dest.y) return result; 
     if(top.x<0 || top.x>=a) continue; 
     if(top.y<0 || top.y>=b) continue; 
     if(vis[top.x][top.y]) continue; 

     vis[top.x][top.y]=true; 
     result+=map[top.x][top.y]; 
     for(int i=0;i<4;i++) 
     { 
      tempa.x=top.x+X[0]; 
      tempa.y=top.y+Y[0]; 
      tempa.time=map[top.x+X[0]][top.y+Y[0]]; 
      pq.push(tempa); 
     } 
    } 
    return -1; 
} 

int main() 
{ 
    memset(vis,false,sizeof(vis)); 
    scanf("%d %d",&a,&b); 
    while(a != 0) 
    { 
     for(int i=0;i<a;i++) 
      for(int j=0;j<b;j++) 
      { 
       scanf("%c",&temp); 
       if(temp=='X') {map[i][j]=0;vis[i][j]=true;} 
       if(temp=='S') {src.x=i;src.y=j;src.time=0;} 
       if(temp=='D') {dest.x=i;dest.y=j;dest.time=0;} 
       else map[i][j]=temp-'0'; 
      } 
     cout<<djs_bfs(src,dest)<<endl; 
     scanf("%d %d",&a,&b); 
    } 
    return 0; 
    getch(); 
} 

Je ne sais pas pourquoi mon code ne génère pas la bonne réponse pour les testcases. Si quelqu'un peut me aider à améliorer le code, s'il vous plaît le faire: D

Answer 1

Tout d'abord, le code d'analyse graphique est incorrect. La première ligne spécifie la largeur et la hauteur, où la largeur est le nombre de caractères par ligne, la hauteur est le nombre de lignes. Par conséquent, permutez &a et &b dans le premier scanf ou inversez l'ordre des boucles imbriquées for (mais pas les deux). En outre, j'ai dû ajouter des appels fictifs scanf("%c", &dummy); à divers endroits pour filtrer les nouvelles lignes. Une décharge simple, comme cela, vous aidera à déterminer si votre carte a été analysée correctement:

cout << "a=" << a << endl; 
cout << "b=" << b << endl; 
for (int i=0; i<a; i++) { 
    for(int j=0; j<b; j++) { 
     cout << (char)('0' + map[i][j]) << ","; 
    } 
    cout << endl; 
} 

Note: J'ai aussi mis map[i][j]-0 pour « S » et « D », en changeant également les déclarations if répétées dans un if; else if; else chaîne. Cela rend l'algorithme plus robuste, puisque vous pouvez génériquement ajouter du temps depuis la source ou la destination.

Maintenant, l'algorithme lui-même ....

Chaque boucle des incréments de l'algorithme result par le poids actuel de l'emplacement de la carte. Cependant, l'algorithme recherche simultanément plusieurs chemins (c'est-à-dire, le nombre d'entrées dans la file d'attente prioritaire), et donc result finit par être la somme de tous les poids de nœuds traités, pas le poids actuel du chemin. Le poids actuel du trajet est top.temp. Par conséquent, vous pouvez éliminer la variable result et renvoyer simplement top.temp lorsque vous atteignez la destination.

En outre, comme d'autres réponses ont été indiquées, vous devez utiliser et Y[i] dans votre boucle interne, sinon vous ne recherchez que dans une direction.Maintenant, en raison de l'addition/soustraction de et Y[i], vous aurez probablement accès map[][] hors de portée (-1 ou 25). Par conséquent, je recommande de déplacer les protections if vers la boucle intérieure for pour éviter tout accès hors de portée. Cela évite également de remplir la file d'attente prioritaire avec des possibilités illégales.

Voici ma version de l'algorithme, avec des corrections minimales, pour référence:

priority_queue<node>pq; 
pq.push(src); 
while(!pq.empty()) 
{ 
    node top = pq.top(); 
    pq.pop(); 

    if(top.x==dest.x && top.y==dest.y) return top.time; 
    if(vis[top.x][top.y]) continue; 

    vis[top.x][top.y]=true; 

    for(int i=0;i<4;i++) 
    { 
     tempa.x=top.x+X[i]; 
     tempa.y=top.y+Y[i]; 
     if(tempa.x<0 || tempa.x>=a) continue; 
     if(tempa.y<0 || tempa.y>=b) continue; 
     tempa.time=top.time + map[tempa.x][tempa.y]; 
     pq.push(tempa); 
    } 
} 
return -1; 

J'espère que cela aide.

Answer 2

Vous utilisez X[0] et Y[0] au lieu de X[i] et Y[i] dans cette boucle intérieure. D'ailleurs, à part ça, votre Dijkstra est très inefficace. Premièrement, vous poussez des noeuds dans la file d'attente même s'ils ont déjà été visités, et deuxièmement, vous pouvez avoir plusieurs des mêmes noeuds dans la file d'attente, juste à des moments différents. En fin de compte, aucune de ces deux choses n'influent sur le résultat, mais vous changez la complexité.

Édition: Oh, tempa.time doit être égal à top.time plus le poids de la bordure, pas seulement le poids de la bordure.

Answer 3

Pourquoi avez-vous 0 index?

tempa.x=top.x+X[0]; 
tempa.y=top.y+Y[0]; 
tempa.time=map[top.x+X[0]][top.y+Y[0]]; 

pinailler:

bool operator <(const node &s,const node &r) 
{ 
    if(s.time>r.time) 
    return true; 
    else return false; 
} 

est-ce pas plus facile à lire:

bool operator <(const node &s,const node &r) 
{ 
    return (s.time>r.time); 
}