Implémentation de l'algorithme de Dijkstra - Le code ne fonctionne pas pour les grandes entrées

Question

#include <iostream> 
#include <list> 

using namespace std; 

class edge 
{ 
    public: 
     int dest; 
     int dist; 
     edge(int a,int b) 
     { 
      dest=a; 
      dist=b; 
     } 
}; 

class Graph 
{ 
    public: 
     int v;  
     list<edge> *adj; 
     list<int> remEdges; 
     int *dist; 
     int *parent; 
     int src; 
     Graph(int); 
     void addEdge(int,int,int); 
     void printEdges(int); 
     bool isPresent(int); 
     int findMin(); 
     void dijkstra(int); 
}; 

Graph::Graph(int v) 
{ 
    adj = new list<edge>[v]; 
    this->v=v; 
    dist=new int(v); 
    parent=new int(v); 
    for(int i=0;i<v;i++) 
    { 
     remEdges.push_back(i); 
     dist[i]=INT_MAX; 
    } 
} 

bool Graph::isPresent(int num) 
{ 
    list<int> :: iterator i; 

    for(i=remEdges.begin();i!=remEdges.end();i++) 
     if(num==*i) 
      return true; 

    return false; 
} 

int Graph::findMin() 
{ 
    int min=INT_MAX; 
    int index=-1; 
    for(int i=0;i<v;i++) 
     if(dist[i]<min && isPresent(i)) 
     { 
      min=dist[i]; 
      index=i; 
     } 
    return index; 
} 

void Graph :: addEdge(int i,int j,int k) 
{ 
    adj[i].push_back(edge(j,k)); 
    adj[j].push_back(edge(i,k)); 
} 

void Graph :: printEdges(int src) 
{ 
for(int i=0;i<v;i++) 
if(i!=src) 
cout<<dist[i]<<" "; 


} 

void Graph::dijkstra(int src) 
{ 
    dist[src]=0; 
    while(!remEdges.empty()) 
    { 
     int min=findMin(); 
     list<edge> :: iterator i; 

     for(i=adj[min].begin();i!=adj[min].end();i++) 
     { 
      if(isPresent((*i).dest)) 
      { 
      if(dist[min]+(*i).dist<dist[(*i).dest]) 
       dist[(*i).dest] = dist[min]+(*i).dist; 
      } 
      parent[(*i).dest]=min;     
     } 
     remEdges.remove(min); 
    } 
} 


int main() 
{ 

    Graph g(9); 
    g.addEdge(0, 1, 4); 
    g.addEdge(0, 7, 8); 
    g.addEdge(1, 2, 8); 
    g.addEdge(1, 7, 11); 
    g.addEdge(2, 3, 7); 
    g.addEdge(2, 8, 2); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 4, 9); 
    g.addEdge(3, 5, 14); 
    g.addEdge(4, 5, 10); 
    g.addEdge(5, 6, 2); 
    g.addEdge(6, 7, 1); 
    g.addEdge(6, 8, 6); 
    g.addEdge(7, 8, 7); 
    g.dijkstra(0); 
    g.printEdges(0); 
    cout<<endl; 

    return 0; 
} 

Le code ne fonctionne pas pour les grandes entrées. Je suis débutant aux algorithmes et j'ai voulu implémenter l'algorithme de dijkstra par l'intermédiaire de CPP. J'ai passé beaucoup d'heures à corriger le code.

Il affiche une sortie correcte en mode débogage mais ne fonctionne pas lorsqu'il est exécuté directement à partir du bouton Exécuter.

J'utilise DEV C++ pour exécuter le code et il exécute bien lorsque la fonction du pilote est

int main() 
{ 
    Graph g(4); 
    g.addEdge(0, 1, 24); 
    g.addEdge(0, 3, 20); 
    g.addEdge(2, 0, 3); 
    g.addEdge(3, 2, 12); 
    g.dijkstra(0); 
    g.printEdges(0); 
    cout<<endl; 
    return 0; 
} 

Mais il ne fonctionne pas quand je suis ajouter trop de bords.

S'il vous plaît aidez-moi à cet égard.

Answer 1

//You should use: 
dist=new int[v]; 
parent=new int[v]; 

//instead of 
//dist=new int(v); means: dist = new int[1]; dist[0] = v; 
//parent=new int(v); 

Utilisation des résultats mémoire non alloués dans le comportement non défini, il était donc seulement la chance, votre code n'a pas planté avec quelques sommets.

Vous devez également définir le parent de l'enfant uniquement si l'enfant n'a pas été visité auparavant, même s'il n'a pas pu provoquer le plantage. =)

if(isPresent((*i).dest)) 
{ 
    if(dist[min]+(*i).dist<dist[(*i).dest]) 
     dist[(*i).dest] = dist[min]+(*i).dist; 

    parent[(*i).dest]=min; 
}