如何優化此dijkstra結構代碼？

這是Dijkstra算法結構，我使用：（但是MAXV（這是頂點的最大數量是最大的，在500和每一個我試圖改變它的東西比這產生和錯誤更多的時間運行時）如何優化此dijkstra結構代碼？

- 我想用這種方式來表示有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]; 
}

來源

2010-06-28 magiix

提示：首選'const int MaxV = 500;'。它更安全，更易於調試。 – MSalters 2010-06-28 14:14:09

我沒有看到NULL指針的任何檢查。 – 2010-06-29 00:13:44

使用adjacency lists用於存儲圖表。現在你正在使用adjacency matrix，這意味着你只爲此分配MAXV*MAXV*sizeof(edge)字節。當MAXV是10 000時，這很多，所以你可能會遇到分段錯誤。切換到鄰接列表將擺脫錯誤。

但是，即使有鄰接表，您現在的Dijkstra算法也是O(n^2)，其中n是節點的數量。對於10 000節點，這仍然很多。考慮實施Dijkstra with heaps（也是here），如果您必須支持這麼多節點。

來源

2010-06-28 13:02:34 IVlad

'10000 * 10000 * 8'可能看起來很多，但小於800 MB。這是不可能的segfault。通過適當的malloc處理（未顯示），它根本不會出錯。當然，代碼也可能會遇到Stack Overflow。 – MSalters 2010-06-28 14:16:34

@ MSalters - 是的，但通過切換到鄰接列表可以減少很多，但800 MB仍然很多，這也會使大多數圖算法快得多。 – IVlad 2010-06-28 14:25:00

謝謝，我可以看到你的觀點：D – magiix 2010-06-28 21:15:21

如何優化此dijkstra結構代碼？

回答

相關問題