竞争性编程 Dijkstra

Question

谁能告诉我这个程序的错误在哪里，这真的很有帮助，我尽力解决了这个问题，这段代码只通过了两个测试用例给定一个无向图和一个起始节点，确定从起始节点到图中所有其他节点的最短路径的长度。如果一个节点不可到达，它的距离是-1。节点将从 到 连续编号，边将具有不同的距离或长度。这里是问题https://www.hackerrank.com/challenges/dijkstrashortreach/problem

    #include <stdio.h> 
    #include <stdlib.h> 
    #pragma warning(disable:4996)
    // Node 
    typedef struct node {
        int data;

        // Lower values indicate higher priority 
        int priority;

        struct node* next;

    } Node;

    // Function to Create A New Node 
    Node* newNode(int d, int p)
    {
        Node* temp = (Node*)malloc(sizeof(Node));
        temp->data = d;
        temp->priority = p;
        temp->next = NULL;

        return temp;
    }

    // Return the value at head 
    int peek(Node** head)
    {
        return (*head)->data;
    }

    // Removes the element with the 
    // highest priority form the list 
    void pop(Node** head)
    {
        Node* temp = *head;
        (*head) = (*head)->next;
        free(temp);
    }
    void updateprt(Node** head, int data) {
        if ((*head)->data == data)
        {
            Node* temp = *head;
            *head = (*head)->next;
            free(temp);
            return;
        }
        Node* prev = *head;

        while ((prev->next)->data != data) {
            prev = prev->next;
        }
        Node* start = prev->next;
        prev->next = start->next;
        free(start);

    }

    // Function to push according to priority 
    void push(Node** head, int d, int p)
    {
        Node* start = (*head);

        // Create new Node 
        Node* temp = newNode(d, p);
        if (*head == NULL) {
            *head = temp;
            return;
        }
        // Special Case: The head of list has lesser 
        // priority than new node. So insert new 
        // node before head node and change head node. 
        if ((*head)->priority > p) {

            // Insert New Node before head 
            temp->next = *head;
            (*head) = temp;
        }
        else {

            // Traverse the list and find a 
            // position to insert new node 
            while (start->next != NULL &&
                start->next->priority < p) {
                start = start->next;

            }

            // Either at the ends of the list 
            // or at required position 
            temp->next = start->next;
            start->next = temp;
        }
    }

    // Function to check is list is empty 
    int isEmpty(Node** head)
    {
        return (*head) == NULL;
    }
    struct adjlistnode {
        int data;
        struct adjlistnode* next;
    };
    struct adjlist {
        struct adjlistnode* head;
    };
    struct graph {
        int v;
        struct adjlist* array;
    };
    struct graph* creategraph(int v) {
        struct graph* G = (struct graph*) malloc(sizeof(struct graph));
        G->v = v;
        int i;
        G->array = (struct adjlist*)malloc(sizeof(struct adjlist)*v);
        for (i = 0; i < v; i++) {
            G->array[i].head = NULL;
        }
        return G;
    }
    int  Distance[100000], path[50];
    struct adjlistnode* getnewnode(int ver) {
        struct adjlistnode* newnode = (struct adjlistnode*)malloc(sizeof(struct adjlistnode));
        newnode->data = ver;
        newnode->next = NULL;
        return newnode;

    }
    void addedge(struct graph* G, int src, int dest, long int w, long int** weight) {
        struct adjlistnode* temp;
        temp = getnewnode(dest);
        temp->next = G->array[src].head;
        G->array[src].head = temp;

        temp = getnewnode(src);
        temp->next = G->array[dest].head;
        G->array[dest].head = temp;
        if (weight[src][dest] != 0 || weight[dest][src] != 0 && w < weight[src][dest]) {
            weight[src][dest] = w;
            weight[dest][src] = w;
        }
        if (weight[src][dest] == 0) {
            weight[src][dest] = w;
            weight[dest][src] = w;
        }
    }
    void printgraph(struct graph* G) {
        for (int i = 0; i < G->v; i++) {
            struct adjlistnode* temp = G->array[i].head;
            printf("%d->   ", i);
            while (temp) {
                printf(" %d", temp->data);
                temp = temp->next;
            }
            printf("\n");
        }
    }

    void Dijkstra(Node** queue, struct graph* G, int s, long int** weight) {
        int v, w, d;
        push(queue, s, 0);
        for (int i = 0; i < 100000; i++) {
            Distance[i] = -1;
        }
        Distance[s] = 0;
        while (!isEmpty(queue)) {
            v = peek(queue);
            pop(queue);
            struct adjlistnode* temp = G->array[v].head;
            while (temp) {
                w = temp->data;
                d = Distance[v] + weight[v][w];

                //To update the distance of w check the below two conditions
                if (Distance[w] == -1) {
                    Distance[w] = d;
                    push(queue, w, d);
                    path[w] = v;
                }
                if (Distance[w] > d)
                {
                    Distance[w] = d;

                    path[w] = v;
                    updateprt(queue, w);
                    push(queue, w, d);


                }
                temp = temp->next;
            }
        }
    }


    int main()
    {
        int t;
        scanf("%d", &t);
        while (t) {

            Node* pq = NULL;

            int v;
            int e;
            scanf("%d %d", &v, &e);
            long int** weight = (long int**)malloc(sizeof(long int*)*v);
            for (int i = 0; i < v; i++)
                weight[i] = (long int*)malloc(sizeof(long int)*v);
            struct graph* G = creategraph(v);
            int u, w;
            long int l;
            for (int i = 0; i < e; i++) {
                scanf("%d %d %ld", &u, &w, &l);
                addedge(G, u - 1, w - 1, l, weight);
            }

            int s;
            scanf("%d", &s);
            //    printgraph(G);
                //printf("\n");
            Dijkstra(&pq, G, s - 1, weight);
            for (int i = 0; i < G->v; i++) {
                if (i == s - 1)
                    continue;
                printf("%d ", Distance[i]);
            }
            /*    while (!isEmpty(&pq)) {
                    printf("%d ", peek(&pq));
                    pop(&pq);
                }*/


            return 0;
        }
        system("pause");
    }

Answer 1

您最大的问题是您的优先级队列，您将其实现为简单的链表。您似乎对何时以及如何使用指向节点指针的指针感到困惑。

例如这个函数:

int isEmpty(Node **head) ...

只检查列表。它不会修改它，因此传递一个节点指针就足够了:

int isEmpty(Node *head) ...

此函数也不会修改节点的内容，因此可以明确表示:

int isEmpty(const Node *head) ...

另一方面，push , pop和 updateprt函数必须能够通过指针更改头部，因此它们需要一个指向节点指针的指针。你的pop总是改变头部的函数就是这样做的。其他函数如下所示:

void push(Node** head, int d, int p)
{
    Node* start = (*head);

    // ... do stuff with start, leave head alone ...
}

在这里，您只是使用指向节点指针的指针作为一种过于模糊的方式来传递有关头部的信息，但您从未修改它(除了插入到 ampty 列表的特殊情况)。

这就是push函数应如下所示:

void push(Node **head, int d, int p)
{
    Node *temp = newNode(d, p);

    while (*head && (*head)->priority < p) {
        head = &(*head)->next;
    }

    temp->next = *head;
    *head = temp;
}

请注意没有任何特殊情况。当您调用 push(&queue, ...) ，你传递头指针的地址就可以修改局部变量queue在调用函数中分配给 *head .当您使用 head = &(*head)->next 遍历列表时, head持有 next 的地址前一个节点的字段，您也可以通过 *head 修改.指向指针的指针添加了一层间接寻址并告诉您您来自哪里并允许您修改该值。

同样，您可以更改(并简化)您的 updateptr功能:

void updateprt(Node** head, int data)
{
    while (*head && (*head)->data != data) {
        head = &(*head)->next;
    }

    if (*head) pop(head);
}

通过这些更改，您的程序应该可以运行，但还有其他需要注意的事项:

if (权重[源][目标] != 0 || 权重[目标][源] != 0 && w < 权重[源][目标]) ...

条件(w1 == 0 || w2 == 0 && w < w1)被解析为 (w1 == 0 || (w2 == 0 && w < w1)) ，这可能不是你想要的。零检查没有正确完成，因为您从未初始化 weight . (您可以使用 calloc 而不是 malloc 来创建一个零初始化数组。)`

但是为什么要有一个单独的权重数组呢？您可以存储每条边的权重:

struct adjlistnode {
    int data;                   // destination vertex
    int weight;
    struct adjlistnode* next;
};

数组也是如此:

int  Distance[100000], path[50];

两个数组都为每个顶点提供一个条目。第一个太慷慨了(“我会多分配一点，以防万一......”)，第二个可能太小了。 (你不需要任务的路径，但能够验证它总是很好。变量不是路径，但是，它保存了朝向每个顶点起点的下一步。)

比赛规则规定最多有 3,000 个节点，因此您可以使用 [3000] 对数组进行维数处理。 , 但你也冷酷地将它们作为图结构的一部分，并根据顶点数进行分配。

祝你好运!