конкурентное программирование Дейкстра

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

Здесь вы только что использовали указатель на указатель узла как чрезмерно неясный способ передачи информации о голове, но вы никогда не изменяете ее (за исключением специальногослучай вставки в пустой список).

Вот как должна выглядеть эта функция 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 (weight [src] [dest]! = 0 || weight [dest] [src]! = 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];

Оба массива предоставляют одну запись для каждой вершины.Первый слишком щедрый («Я выделю немного больше, на всякий случай ...»), второй может быть слишком маленьким.(Вам не нужен путь для задачи, но всегда приятно иметь возможность проверить его. Переменная не является путем, однако она содержит следующий шаг к начальной точке для каждой вершины.)

Правила конкуренции гласят, что существует не более 3000 узлов, поэтому вы можете просто измерить массивы с помощью [3000], но вы также можете сделать их частью структуры графа и распределить их в соответствии с количеством вершин.

Удачи!