这是我正在使用的dijkstra结构:(但是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;
这是我的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];
}
最佳答案
使用adjacency lists存储图形。现在,您正在使用adjacency matrix,这意味着您仅为此分配了MAXV*MAXV*sizeof(edge)
个字节。当MAXV
是10 000
时,这很多,所以您可能会遇到分段错误。切换到邻接表将消除该错误。
但是,即使具有邻接列表,您现在拥有的Dijkstra算法也是O(n^2)
,其中n
是节点数。对于10 000
节点,这仍然很多。如果必须支持这么多节点,请考虑实现Dijkstra with heaps(也称为here)。
关于c++ - 我如何优化此dijkstra结构代码?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3132491/