我想修改我的最短路径查找代码以使用多线程并提高其性能。该算法必须能够处理负权重，因此我们不能使用 Dijkstra 算法。相反，我们的方法结合了三种算法：Bellman-Ford、SPFA_Queue（最短路径快速算法，对使用队列的 Bellman-Ford 的改进，在某些情况下速度更快）和 SPFA_MinHeap（使用 minheap 的 SPFA 的第二种变体） .
在进行大量测试后，我们根据图的大小和密度确定了三种算法中选择一种的最优条件。
现在的问题是如何根据每个算法的工作方式，以最有效的方式集成多线程。如有必要，我们愿意重写部分算法以启用多线程并提高性能，我们希望保留这三种算法的使用，因为到目前为止它们已被证明非常有效，我们希望保留获得的性能增益从以前的工作中获得，同时通过多线程实现最大优化。
我们对单线程代码本身非常满意，并且所有标头和使用的方法都在单独的文件中正确定义和测试（可根据要求提供）。 该请求涉及寻找在当前逻辑中实现多线程的最有效策略。
这里是有问题的代码：
/**
* Computes the shortest path between a given source node and all other nodes in a weighted graph using either the Bellman-Ford or SPFA_SLF algorithm based on the density and number of nodes in the graph.
*
* Arguments:
* links: A 2D array of integers representing the links between nodes. Each row represents a link and contains the indices of the two nodes and the cost of the link.
* links_size: The number of links in the links array.
* s: The index of the starting node.
* dist: An array of size nb_nodes to store the shortest distances from each node to s.
* path: An array of size nb_nodes to store the shortest paths from each node to s.
* nb_nodes: The total number of nodes in the graph.
*
* Returns:
* 0 if the computation succeeded, 1 if a negative cycle was detected in the graph.
**/
int shortest_path(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes)
{
// Select algorithm based on graph density and number of nodes
if (links_size <= 100 || nb_nodes <= 100)
{
return bellman_ford(links, links_size, s, dist, path, nb_nodes);
}
else if (((double)links_size / (double)(nb_nodes)) < 1)
{
return SPFA_queue(links, links_size, s, dist, path, nb_nodes);
}
else
{
return SPFA_minheap(links, links_size, s, dist, path, nb_nodes);
}
}
// Version 1: classical Bellman-Ford algorithm
int bellman_ford(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes)
{
int updates;
uint i;
uint j;
uint k;
// Initialize all elements of dist to INT64_MAX ("infinity").
for (i = 0; i < nb_nodes; i++)
{
dist[i] = INT64_MAX;
}
// Initialise path
memset(path, -1, nb_nodes * sizeof(sint));
dist[s] = 0;
// Perform nb_nodes - 1 iterations of Bellman-Ford algorithm
for (i = 0; i < nb_nodes - 1; i++)
{
updates = 0;
// For each link in the links array, attempt to update shortest distances for each node.
for (j = 0; j < links_size; j++)
{
uint node_from = links[j][0];
uint node_to = links[j][1];
lsint cost = links[j][2];
// If a shorter distance is found, store it in the dist array and update the path array
if ((dist[node_from] != INT64_MAX) && (dist[node_from] + cost < dist[node_to]))
{
dist[node_to] = dist[node_from] + cost;
path[node_to] = node_from;
updates++;
}
}
// If no update was made during the previous iteration, exit the loop
if (updates == 0)
{
break;
}
}
// Check for negative cycle in the graph
for (k = 0; k < links_size; k++)
{
uint node_from = links[k][0];
uint node_to = links[k][1];
lsint cost = links[k][2];
// If a shorter distance is still found, there is a negative cycle
if ((dist[node_from] != INT64_MAX) && (dist[node_from] + cost < dist[node_to]))
{
// printf("Negative cycle detected\n");
return 1;
}
}
return 0;
}
// Version 2: SPFA using small label first method and a queue
int SPFA_queue(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes)
{
queue_t *queue = create_queue(); // Initialize the queue
if (queue == NULL)
{
fprintf(stderr, "Failed to allocate memory for queue.\n");
return 1;
}
uint i;
uint *length = calloc(nb_nodes, sizeof *length); // Array to store the number of nodes in the shortest path for each node in the graph.
if (length == NULL)
{
fprintf(stderr, "Failed to allocate memory for length.\n");
free_queue(queue);
return 1;
}
// Initialize all elements of dist to INT64_MAX ("infinity").
for (i = 0; i < nb_nodes; i++)
{
dist[i] = INT64_MAX;
}
// Initialise path
memset(path, -1, nb_nodes * sizeof(sint));
dist[s] = 0; // Set the distance of the source node to 0
enqueue(queue, s); // Add the source node to the queue
length[s] = 1;
bool *in_queue = calloc(nb_nodes, sizeof(bool));
in_queue[s] = true;
// While the queue is not empty, perform iterations of the algorithm
while (!is_empty(queue))
{
uint current_node = dequeue(queue); // Dequeue the next node to process
in_queue[current_node] = false;
// If the length of the shortest path for any link reaches nb_nodes, there is a negative cycle in the graph
if (length[current_node] >= nb_nodes)
{
// printf("Negative cycle detected\n");
free(length);
free(in_queue);
free_queue(queue);
return 1;
}
int min_node = -1;
lsint min_dist = INT64_MAX;
// Iterate through all the links in the graph
for (i = 0; i < links_size; i++)
{
// If the current link starts from the dequeued node (current_node)
if (links[i][0] == current_node)
{
uint node_from = links[i][0];
uint node_to = links[i][1];
lsint cost = links[i][2];
// If a shorter path is found, update the distances and paths
if (dist[node_from] + cost < dist[node_to])
{
dist[node_to] = dist[node_from] + cost;
path[node_to] = node_from;
length[node_to] = length[node_from] + 1;
// If the destination node (node_to) is not in the queue, enqueue it
if (!in_queue[node_to])
{
enqueue(queue, node_to);
in_queue[node_to] = true;
}
}
// Update the minimum distance and node for Small Label First (SLF)
if (dist[node_to] < min_dist)
{
min_dist = dist[node_to];
min_node = node_to;
}
}
}
if (min_node != -1)
{
// Move the node with the minimum distance to the front of the queue
move_to_front(queue, min_node);
}
}
free(length);
free(in_queue);
free_queue(queue);
return 0;
}
// Version 3: SPFA using a min_heap
int SPFA_minheap(sint links[][3], uint links_size, uint s, lsint *dist, uint *path, uint nb_nodes)
{
// Create a min heap to store the nodes and their distances.
MinHeap *heap = create_minheap(nb_nodes);
if (heap == NULL)
{
fprintf(stderr, "Failed to allocate memory for min heap.\n");
return EXIT_FAILURE;
}
uint i;
// Allocate memory for an integer array to keep track of whether a node is already in the heap.
uint *in_heap = calloc(nb_nodes, sizeof *in_heap);
if (in_heap == NULL)
{
fprintf(stderr, "Failed to allocate memory for in_heap.\n");
free_minheap(heap);
return EXIT_FAILURE;
}
// Create an array to store the number of nodes in the shortest path for each node in the graph.
uint *length = calloc(nb_nodes, sizeof *length); // Array to store the number of nodes in the shortest path for each node in the graph.
if (length == NULL)
{
fprintf(stderr, "Failed to allocate memory for length.\n");
free_minheap(heap);
free(in_heap);
return EXIT_FAILURE;
}
// Initialize all elements of dist to INT64_MAX ("infinity").
for (i = 0; i < nb_nodes; i++)
{
dist[i] = INT64_MAX;
}
// Initialize all elements of `path` to -1.
memset(path, -1, nb_nodes * sizeof(sint));
// Create an adjacency list to represent the graph.
adjacency_node_t **adj_list = create_adjacency_list(nb_nodes, links, links_size);
if (adj_list == NULL)
{
fprintf(stderr, "Failed to allocate memory for adj_list.\n");
free(length);
free(in_heap);
free_minheap(heap);
return EXIT_FAILURE;
}
// Set the distance of the source node to 0.
dist[s] = 0;
// Add the source node to the heap.
heap = insert_minheap(heap, s);
in_heap[s] = 1;
// Set the length of the shortest path for the source node to 1.
length[s] = 1;
// While the heap is not empty, perform iterations of the algorithm
while (heap->size != 0)
{
// Extract the node with the minimum distance from the heap.
uint current_node = get_min(heap);
heap = delete_minimum(heap);
in_heap[current_node] = 0;
// If the length of the shortest path for any link reaches nb_nodes, there is a negative cycle in the graph
if (length[current_node] >= nb_nodes)
{
// printf("Negative cycle detected\n");
free(length);
free_adjacency_list(adj_list, nb_nodes);
free(in_heap);
free_minheap(heap);
return EXIT_FAILURE;
}
adjacency_node_t *adj_node = adj_list[current_node];
// Loop over all the edges that start from the current node
while (adj_node != NULL)
{
uint node_to = adj_node->node_to;
lsint cost = adj_node->cost;
// If a shorter path is found, update the distances and paths
if (dist[current_node] + cost < dist[node_to])
{
dist[node_to] = dist[current_node] + cost;
path[node_to] = current_node;
length[node_to] = length[current_node] + 1;
// If the destination node (node_to) is not in the heap, insert it
if (!in_heap[node_to])
{
insert_minheap(heap, node_to);
in_heap[node_to] = 1;
}
}
adj_node = adj_node->next;
}
}
free(length);
free_adjacency_list(adj_list, nb_nodes);
free_minheap(heap);
free(in_heap);
return EXIT_SUCCESS;
}