Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

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

In lại Tác giả: Walker 123 更新时间：2023-11-28 08:28:29 27 4
mua khóa gpt4 Nike

这是我正在使用的 dijkstra 结构 :(但是 MAXV(最大顶点数最大为 500，每次我尝试将其更改为超过此值时都会生成并在运行时出错)

-我想用这种方式来表示一个有10000个顶点的图，有谁知道如何优化它吗？

#include
#include
#include
#include
sử dụng không gian tên 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;indegree[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;invertices;++i){
                   if((intree[i]==false) && (dist > distance[i])){
                           dist=distance[i];
                            v=i;
                   }
           }
    }
    return distance[end];
}

câu trả lời hay nhất

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

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

关于c++ - 我如何优化这个 dijkstra 结构代码？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3132491/

27 4 0
Đề xuất bài viết: javascript - 使用 Sizzle 扩展 API 创建自定义 jQuery 选择器
Đề xuất bài viết: c++ - 如何将 map 传递给py？
Đề xuất bài viết: javascript - 如何返回 google map 标记的城市、街道和邮政编码？
Đề xuất bài viết: C++ 案例 multimap
Walker 123
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress