设计与分析多级图

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
// Function to find the minimum cost path in the multistage graph
typedef struct {
    int *path;
    int length;
} Result;
Result multistage_graph(int graph[][2], int num_edges, int num_vertices, int stages[][3], int num_stages) {
    // Initialize the lists to store the minimum costs and the next vertex in the path for each vertex
    int *min_costs = (int *)malloc(num_vertices * sizeof(int));
    int *next_vertex = (int *)malloc(num_vertices * sizeof(int));
    for (int i = 0; i < num_vertices; i++) {
        min_costs[i] = INT_MAX;
        next_vertex[i] = -1;
    }
    // Initialize the minimum cost for the sink vertex to 0
    min_costs[num_vertices - 1] = 0;
    // Traverse the graph in reverse order starting from the second-last stage
    for (int i = num_stages - 2; i >= 0; i--) {
        for (int j = 0; j < num_vertices; j++) {
            if (stages[i][0] == j || stages[i][1] == j || stages[i][2] == j) {
                for (int k = 0; k < num_edges; k++) {
                    if (graph[k][0] == j) {
                        int neighbor = graph[k][1];
                        int cost = graph[k][2] + min_costs[neighbor];
                        if (cost < min_costs[j]) {
                            // Update the minimum cost and next vertex for the current vertex
                            min_costs[j] = cost;
                            next_vertex[j] = neighbor;
                        }
                    }
                }
            }
        }
    }
    // Reconstruct the minimum cost path from source to sink
    int *path = (int *)malloc(num_vertices * sizeof(int));
    int current_vertex = 0; // Start from the source vertex
    int path_length = 0;
    while (current_vertex != -1) {
        path[path_length++] = current_vertex;
        current_vertex = next_vertex[current_vertex];
    }
    // Free the dynamically allocated memory for min_costs and next_vertex
    free(min_costs);
    free(next_vertex);
    // Store the result in a Result structure
    Result result;
    result.path = path;
    result.length = path_length;
    return result;
}
int main() {
    // Define the multistage graph represented as an adjacency list
    int graph[][2] = {
        {0, 1}, {0, 2},
        {1, 3}, {1, 4},
        {2, 3}, {2, 4},
        {3, 5},
        {4, 5},
        {5, 6},
        {6, 7},
        {7, 8}
    };
    int num_edges = sizeof(graph) / sizeof(graph[0]);
    // Define the stages of the multistage graph
    int stages[][3] = {
        {8},       // Sink stage
        {6, 7},    // Stage K-1
        {3, 4, 5}, // Stage K-2
        {1, 2}     // Source stage
    };
    int num_stages = sizeof(stages) / sizeof(stages[0]);
    int num_vertices = 9; // Total number of vertices in the graph
    // Find the minimum cost path and cost using the multistage_graph function
    Result result = multistage_graph(graph, num_edges, num_vertices, stages, num_stages);
    // Print the result
    printf("Minimum cost path: ");
    for (int i = 0; i < result.length; i++) {
        printf("%d ", result.path[i]);
    }
    printf("\nMinimum cost: %d\n", result.path[result.length - 1]);
    // Free the dynamically allocated memory for the path
    free(result.path);
    return 0;
}

输出

Minimum cost path: 0 2 
Minimum cost: 2