Comment puis-je optimiser ce code de structure dijkstra?

Question

Ceci est la structure de dijkstra que j'utilise: (cependant le MAXV (qui est le nombre maximum de sommets est maximum à 500 et chaque fois que j'essaye de le changer pour quelque chose de plus que cela il génère)

-Je veux utiliser cette façon de représenter un graphique avec 10000 sommets, personne ne sait comment l'optimiser

#include<iostream> 
#include<stdio.h> 
#include<stdlib.h> 
#include<conio.h> 
using namespace std; 
#define MAXV 500 
#define MAXINT 99999 
typedef struct{ 
     int next; 
     int weight; 
}edge; 
typedef struct{ 
     edge edges[MAXV][MAXV]; 
     int nedges; 
     int nvertices; 
     int ndegree[MAXV]; 
}graph; 

et voici mon code Dijkstra:

int dijkstra(graph *g,int start,int end){ 
    int distance[MAXV]; 
    bool intree[MAXV]; 
    for(int i=0;i<=MAXV;++i){ 
      intree[i]=false; 
      distance[i]=MAXINT; 
    } 
    int v=start; 
    distance[v]=0; 
    while(intree[v]==false){ 
      intree[v]=true; 
      for(int i=0;i<g->ndegree[v];++i){ 
        int cand=g->edges[v][i].next; 
        int weight=g->edges[v][i].weight; 
        if(distance[cand] > distance[v]+weight){ 
          distance[cand] = distance[v]+weight; 
        } 
      } 
      int dist=MAXINT; 
      for(int i=0;i<g->nvertices;++i){ 
        if((intree[i]==false) && (dist > distance[i])){ 
          dist=distance[i]; 
          v=i; 
        } 
      } 
    } 
    return distance[end]; 
} 

Answer 1

utilisation adjacency lists pour le stockage le graphique. En ce moment vous utilisez un adjacency matrix, ce qui signifie que vous allouez MAXV*MAXV*sizeof(edge) octets juste pour cela. C'est beaucoup quand MAXV est 10 000, donc vous obtenez probablement un défaut de segmentation. Passer aux listes d'adjacence va se débarrasser de l'erreur.

Cependant, même avec les listes d'adjacence, l'algorithme Dijkstra que vous avez actuellement est O(n^2) où n est le nombre de nœuds. C'est encore beaucoup pour les noeuds 10 000. Envisagez d'implémenter Dijkstra with heaps (également here) si vous devez supporter ce nombre de nœuds.