Как я могу оптимизировать этот код структуры dijkstra?

Question

Это структура Дейкстра я использую: (однако MAXV (что максимальное число вершин максимум при 500 и каждый раз, когда я пытаюсь изменить его на что-то большее, чем это он создает и ошибки при запуске)

-Я хочу, чтобы использовать этот способ для представления графа с 10000 вершин, кто-нибудь знает, как оптимизировать его

#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; 

и это мой Дейкстра код:

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

Использование adjacency lists для хранения график. Прямо сейчас вы используете adjacency matrix, что означает, что вы выделяете только MAXV*MAXV*sizeof(edge) байтов. Это очень много, если MAXV - 10 000, поэтому вы, вероятно, получаете ошибку сегментации. Переключение на списки смежности избавится от ошибки.

Однако, даже с списками смежности, алгоритм Дейкстры, который у вас есть сейчас, равен O(n^2), где n - это количество узлов. Это еще много для узлов 10 000. Рассмотрите возможность внедрения Dijkstra with heaps (также here), если вам нужно поддерживать это множество узлов.