c++ - 我如何优化这个 dijkstra 结构代码？

Question

这是我正在使用的 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];
}

Answer 1

使用adjacency lists用于存储图形。现在你正在使用 adjacency matrix ，这意味着您为此分配了 MAXV*MAXV*sizeof(edge) 字节。当 MAXV 为 10 000 时，这就很多了，因此您可能遇到了段错误。切换到邻接表将消除错误。

但是，即使使用邻接表，您现在拥有的 Dijkstra 算法也是 O(n^2)，其中 n 是节点数。这对于 10 000 节点来说仍然很多。考虑实现 Dijkstra with heaps (还有 here )如果您必须支持这么多节点。