0

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

1 回答 1

1

使用邻接列表来存储图形。现在您正在使用邻接矩阵，这意味着您MAXV*MAXV*sizeof(edge)为此分配字节。很多时候MAXVis 10 000，所以你可能会遇到分段错误。切换到邻接列表将消除错误。

但是，即使使用邻接列表，您现在拥有的 Dijkstra 算法也是节点数O(n^2)在哪里。这对于节点n来说仍然很多。如果您必须支持这么多节点，10 000请考虑使用堆实现Dijkstra（也在此处）。

于 2010-06-28T13:02:34.340 回答