Dijkstra SDSP算法

Question

我试图使用邻接列表和PQ作为最小堆来实现单目标最短路径的Dijkstra算法。输出必须显示所有顶点到目标顶点的路径，如果路径存在，如果是，它的总和（最短），如果否，否路径。链接到整个代码

输入格式：

• 第一行是顶点数，n
• 第二行开始：（从1到n的顶点）
  • 第一列是顶点
  • 之后，多对，

  4
  1 2 4 3 5 4 5
  4 1 7 3 3
  2 1 3 4 10 
  

  根据GDB，它显示了在提取最小函数时发现的分段故障。

  Program received signal SIGSEGV, Segmentation fault.
  0x00401746 in extractMin ()
  

  客户. c

  从文本中提取输入。txt文件并创建一个有向图

  FILE *fptr = fopen("test.txt", "r");
      if (fptr == NULL) exit(1);
  
      int n;
      if (fscanf(fptr, "%d", &n) == 1 && n > 0)
      {
          Graph *graph = createGraph(n);
          int c;
          while ((c = fgetc(fptr)) != EOF && c != '\n');
          char *line = NULL;      
          size_t len = 0;        
  
          while (getline(&line, &len, fptr) > 0)
          {
              char *cur = line;
              int ccs = 0;
              int v1;
  
              if (sscanf(cur, "%d%n", &v1, &ccs) == 1)
              {
                  cur += ccs;
                  int v2;
                  int w;
                  while (sscanf(cur, "%d %d%n", &v2, &w, &ccs) == 2)
                  {
                      addEdge(graph, v1, v2, w);
                      cur += ccs;
                  }
  
                  fputc('\n', stdout);
              }
  
          }
          free(line);
          for (int i = 0; i < n; i++)
              dijkstra(graph, i);
      }
  

  服务器. c

  struct MinHeapNode* extractMin(MinHeap* minHeap)
  {
      if (isEmpty(minHeap))
          return NULL;
   
      struct MinHeapNode* root = minHeap->array[0];
      struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
      minHeap->array[0] = lastNode;
   
      minHeap->pos[root->v] = minHeap->size-1;
      minHeap->pos[lastNode->v] = 0;
   
      --minHeap->size;
      minHeapify(minHeap, 0);
   
      return root;
  }
  void dijkstra(Graph* graph, int dest)
  {
      int v = graph->vertices;
      int distance[v]; 
      int pathFollow[1000]={0};
      int ind = 0;
  
      MinHeap* minHeap = createMinHeap(v);
   
      for (int i = 0; i < v; ++i)
      {
          distance[v] = INT_MAX;
          minHeap->array[v] = newMinHeapNode(v, distance[v]);
          minHeap->pos[v] = v;
      }
   
      minHeap->array[dest] = newMinHeapNode(dest, distance[dest]);
      minHeap->pos[dest] = dest;
      distance[dest] = 0;
      decreaseKey(minHeap, dest, distance[dest]);
   
      minHeap->size = v;
  
      while (!isEmpty(minHeap))
      {
          struct MinHeapNode* minHeapNode = extractMin(minHeap);
          int u = minHeapNode->v;
          AdjListNode* path = graph->array[u].head;
          while (path != NULL)
          {
              int v = path->vertex;
              if (isInMinHeap(minHeap, v) && distance[u] != INT_MAX &&
                path->weight + distance[u] < distance[v])
              {
                  distance[v] = distance[u] + path->weight;
                  if(pathFollow[ind-1] != u)
                      pathFollow[ind++]=u;
                  decreaseKey(minHeap, v, distance[v]);
              }
              path = path->next;
          }
      }
      printArr(distance, v, pathFollow, dest);
  }
  
  void printArr(int dist[], int n, int pathFollow[], int dest)
  {
      printf("%d", dest+1);
      int j = 0;
      if(dist[n-1]!=0 && dist[n-1] < 100000000) 
      {
          int k = j;
          printf(" %d", pathFollow[k]+1);
          while(pathFollow[j]!=0) 
          {
          printf(" %d", pathFollow[j++]);
          }
          printf(" %d %d\n",n, dist[n-1]);
      }
      else
      {
          printf("NO PATH\n");
      }
  }
  
  
  

Answer 1

我不打算调试整个程序，但这里有几个错误：

>

你创造

 Graph *graph = createGraph(n);

然后访问图形-

这是一个问题，因为n只是顶点的总数，在您的例子4中，但是当用类似4 1 7的东西调用addEdge（）时，这就是堆缓冲区溢出。您需要考虑创建的0索引数组。

另一个溢出问题（这次是堆栈缓冲区溢出）是：

int v = graph->vertices;
int distance[v];

但这被称为

distance[v] = INT_MAX;

同样，不考虑0-indexed数组。此外，该代码似乎可疑，我认为应该是distance[i]=INT_MAX。

请查看您自己的代码以了解更多此类错误，尤其是数组索引溢出，使用地址清理器检查代码中的内存错误，逐步检查程序的每一行，并查看是否确实发生了预期的情况。您提到了extractMin（）中的程序错误。检查它是否正在访问它应该访问的内存SIGSEGV表示非法内存访问。struct MinHeapNode*root是否指向您分配的内容？struct MinHeapNode*lastNode是否指向您分配的内容？