Алгоритм Дейкстры в С

[Veronika360]

our task is to construct an undirected graph without loops based on the list of edges given in the input and then perform the following operations on this graph according to the input:
i - insert - inserting a new edge into the graph
s - search - search for the shortest path in the graph according to the specified start and end
u - update - modification of an existing edge in the graph (i.e. modification of the weight of the given edge), while the weight of the edge must not be changed to a negative number
d - delete - remove an existing edge from the graph

An edge is defined as a pair of two vertices, while the vertices are numbered with non-negative whole numbers from 0 to N, where N is the maximum number of vertices in the given graph.

If the given operation fails, the error message " failed" is written in a separate line.
The failure is, for example, when we try to add an edge that already exists, or when the search operation did not find any path for a given pair of vertices.

The input of the program is the number N (max. number of vertices in the graph) followed by a space and the number M (number of edges in the initial graph) on the first line.
There are M lines, where in each line there is one edge of the initial graph, in the format "(vertex_1, vertex2, weight)".
This initial graph is followed by any number of lines, each line representing one command for one operation (ie, insert, search, update, or delete).
The operation is expressed by the initial letter, i.e. i, s, u or d. The following are the data required for the given operation.
The insert operation needs the following 3 data: vertex_1 number, vertex_2 number, edge weight (also an integer)
The search operation needs the following 2 data: the number of the starting vertex, the number of the end (target) vertex
The update operation needs the following 3 data: number of vertex_1, number of vertex_2, change of edge weight (also an integer)
The delete operation needs the following 2 data: vertex_1 number, vertex_2 number

The output is the shortest paths found by search operations, while the output format is as follows:
: [vertex1, vertex2, vertex3, ..., last_vertex]
In addition, the above-mentioned error messages are also output in case of operation failure, together with the edge above which the given operation failed.

Do 22.04.2024, 09:00

Ukážkový vstup
10 30
(5, 0, 116)
(5, 9, 163)
(5, 2, 117)
(5, 3, 110)
(5, 7, 169)
(5, 8, 188)
(0, 8, 200)
(0, 4, 113)
(0, 1, 110)
(0, 3, 129)
(0, 6, 101)
(8, 9, 160)
(8, 1, 101)
(8, 2, 146)
(8, 4, 139)
(1, 2, 159)
(1, 7, 145)
(1, 3, 182)
(1, 9, 137)
(2, 7, 184)
(2, 9, 184)
(2, 3, 176)
(2, 6, 133)
(2, 4, 199)
(7, 6, 118)
(7, 3, 172)
(9, 4, 145)
(9, 3, 180)
(4, 3, 148)
(3, 6, 129)
s 3 8
s 5 3
s 3 0
s 4 6
d 4 3
i 4 7 90
s 6 9
s 9 5
s 2 1
s 5 2
u 2 7 56
s 1 2
s 6 9
s 9 3
u 5 0 52
d 1 7
i 1 5 85
d 7 3
d 3 6
i 8 3 47
i 0 7 78
s 4 3
s 5 4
u 8 3 -3
u 2 4 -26
d 5 0
u 5 7 -42
d 8 2
u 0 6 -57
d 0 8
u 2 6 91
d 5 8
u 0 6 42
u 8 1 -53
s 4 9
u 8 9 -39
s 1 4
s 0 5
u 7 4 -51
s 1 5
s 5 7
s 6 4
u 9 4 31
u 2 3 4
s 9 7
u 9 4 -96
i 6 4 82
i 2 8 75
d 0 1
d 1 9
i 6 8 1
i 6 5 78
i 1 6 53
s 2 7
i 7 8 34
s 9 5
s 8 9
u 8 4 -65
s 3 6
d 5 3
s 1 5
u 5 9 -25
u 8 6 -100
s 8 9
s 5 2
u 2 4 19
s 7 1
s 6 7
u 0 3 -28
s 3 1
s 0 3
s 7 6
s 8 2
u 5 9 -78
s 3 6
s 3 7
s 5 0
s 4 9
s 3 4
s 2 3
u 5 9 -37
s 9 6
s 6 7
u 9 3 -13
u 8 7 63
s 7 5
d 5 2
d 1 3
u 7 5 -89
s 6 0
d 5 9
s 0 5
s 0 9
d 5 1
d 8 4
s 8 0
s 6 8
d 7 6
u 9 3 -57
u 2 3 -49
d 0 4
s 3 2
u 8 3 -75
i 7 6 25
d 2 9
s 4 3
s 9 1
u 2 7 53
s 8 3
d 8 6
u 8 3 -2
s 5 3
s 7 5
i 5 2 44
d 1 2
s 5 7
u 0 3 42
u 5 6 56
u 2 6 17
s 9 6

Ukážkový výstup
283: [3, 1, 8]
110: [5, 3]
129: [3, 0]
214: [4, 0, 6]
309: [6, 3, 9]
163: [9, 5]
159: [2, 1]
117: [5, 2]
159: [1, 2]
309: [6, 3, 9]
180: [9, 3]
186: [4, 8, 3]
259: [5, 7, 4]
145: [4, 9]
187: [1, 8, 4]
195: [0, 1, 5]
85: [1, 5]
127: [5, 7]
157: [6, 7, 4]
215: [9, 4, 7]
194: [2, 8, 6, 7]
163: [9, 5]
121: [8, 9]
45: [3, 8, 6]
85: [1, 5]
update 8 6 failed
121: [8, 9]
117: [5, 2]
82: [7, 8, 1]
35: [6, 8, 7]
92: [3, 8, 1]
101: [0, 3]
35: [7, 8, 6]
75: [8, 2]
45: [3, 8, 6]
78: [3, 8, 7]
164: [5, 6, 0]
80: [4, 9]
117: [3, 8, 7, 4]
119: [2, 8, 3]
101: [9, 5, 6]
35: [6, 8, 7]
127: [7, 5]
86: [6, 0]
116: [0, 7, 5]
193: [0, 4, 9]
87: [8, 6, 0]
1: [6, 8]
119: [3, 8, 2]
update 8 3 failed
109: [4, 7, 6, 8, 3]
169: [9, 8, 1]
44: [8, 3]
177: [5, 7, 8, 3]
38: [7, 5]
38: [5, 7]
144: [9, 4, 7, 6]

[Veronika360]

Помогите с этим кодом, сверху написано задание, нужный ввод и нужный вывод, посоветовали добавить приоритетную очередь, но абсолютно никакая из моих версий не сработала

[BDA]

Лямзим код из статьи:

void queue_add(PQNode* pq, int* pqSize, int vertex, int dist)
{
    pq[*pqSize] = (PQNode){vertex, dist};
    (*pqSize)++;

    int i = *pqSize - 1;
    int parent = (i - 1) / 2;

    while (i > 0 && pq[parent].dist > pq[i].dist)
    {
        PQNode temp = pq[i];
        pq[i] = pq[parent];
        pq[parent] = temp;

        i = parent;
        parent = (i - 1) / 2;
    }
}

void heapify(PQNode* pq, int pqSize, int i)
{
    for (;;)
    {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int smallestChild = i;

        if (leftChild < pqSize && pq[leftChild].dist < pq[smallestChild].dist)
            smallestChild = leftChild;

        if (rightChild < pqSize && pq[rightChild].dist < pq[smallestChild].dist)
            smallestChild = rightChild;

        if (smallestChild == i)
            break;

        PQNode temp = pq[i];
        pq[i] = pq[smallestChild];
        pq[smallestChild] = temp;
        i = smallestChild;
    }
}

PQNode queue_get(PQNode* pq, int* pqSize)
{
    PQNode result = pq[0];
    pq[0] = pq[*pqSize - 1];
    (*pqSize)--;
    heapify(pq, *pqSize, 0);
    return result;
}

// Dijkstra's algorithm to find the shortest path
void dijkstra(Graph* graph, int src, int dest) {
...
    // Enqueue source node into the priority queue
    queue_add(pq, &pqSize, src, 0);

    while (pqSize > 0) {
        // Extract minimum from priority queue (binary heap)
        PQNode min_node = queue_get(pq, &pqSize);

        int u = min_node.vertex;
        visited[u] = 1;

        // Relax adjacent vertices of u
        for (int i = 0; i < graph->nodes[u].num_edges; i++) {
            int v = graph->nodes[u].edges[i].dest;
            int weight = graph->nodes[u].edges[i].weight;
            if (!visited[v] && distances[u] != INT_MAX && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
                prev[v] = u;
                queue_add(pq, &pqSize, v, distances[v]);
            }
        }
    }
...

Вроде вывод не испортился.