Dijkstra SDSP算法

Question

我试图用邻接列表和PQ作为Min堆来实现单目标最短路径的Dijkstra算法。输出必须显示所有顶点到目标顶点的路径，如果存在路径，如果存在路径，则显示其之和(最短)，如果没有，则不显示路径。链接到整个代码

输入格式：

• 第一行是顶点数，n
• 第二行：(从1到n的顶点)
  • 第一列是顶点。
  • 后，多对，<顶点，weight>

• test.txt

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

据GDB分析，发现extractMin函数存在分割故障。

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

Client.c

从text.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);
    }

Server.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

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

1. 你创造了 图*图= createGraph(n)；

然后访问graph->array[src].head。

这是一个问题，因为n只是顶点的总数，在您的示例4中，但是当使用类似于4 1 7的东西调用该addEdge()时，即堆缓冲区溢出。您需要说明您创建的0-indexed数组。

1. 堆栈缓冲区的另一个溢出问题是： int v=图->顶点；

但这就是我们所说的

distance[v] = INT_MAX;

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

请检查您自己的代码以获得更多这样的错误，特别是对于数组索引溢出，使用地址消毒液检查内存错误的代码，遍历程序的每一行，看看是否确实发生了什么。您提到了extractMin()周围的程序错误。检查它是否正在访问它应该访问的内存。SIGSEGV表示非法内存访问。struct MinHeapNode* root是否指向您分配的东西？struct MinHeapNode* lastNode是否指向您分配的东西？