用C语言写分支限界法编程求源点到终点最短路径及其路径长度

好的，下面是用C语言实现分支限界法求解源点到终点最短路径及其路径长度的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 7 // 图中节点数
#define INF INT_MAX // 定义无穷大

int graph[V][V] = { // 图的邻接矩阵表示
    {0, 2, 4, 1, INF, INF, INF},
    {INF, 0, INF, 3, 10, INF, INF},
    {INF, INF, 0, 2, INF, 5, INF},
    {INF, INF, INF, 0, INF, 2, 8},
    {INF, INF, INF, INF, 0, INF, 7},
    {INF, INF, INF, INF, INF, 0, 9},
    {INF, INF, INF, INF, INF, INF, 0}
};

struct Node {
    int level; // 节点的深度（层数）
    int path[V]; // 存储路径
    int bound; // 节点的界
};

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void printPath(int path[], int len) {
    printf("最短路径为：");
    for (int i = 0; i < len; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");
}

void printLength(int len) {
    printf("路径长度为：%d\n", len);
}

int getBound(struct Node node) {
    int lower = 0, upper = 0;
    int last = node.path[node.level - 1];
    for (int i = 0; i < V; i++) {
        if (node.path[i] != -1) {
            lower += graph[node.path[i]][node.path[i+1]];
        } else {
            break;
        }
    }
    for (int i = 0; i < V; i++) {
        if (graph[i][V-1] != INF) {
            upper += graph[i][V-1];
        }
    }
    return lower + upper;
}

void branchAndBound() {
    int currLevel = 0;
    struct Node currNode, bestNode;
    currNode.level = currLevel;
    currNode.path[0] = 0;
    currNode.path[V-1] = -1;
    currNode.bound = getBound(currNode);

    int queue[V*V] = {0}; // 存储未扩展节点的队列
    int head = 0, tail = 0;
    queue[tail++] = 0; // 将源点加入队列

    while (head != tail) {
        int currVertex = queue[head++];
        if (currNode.level == V-1) { // 已经到达终点
            bestNode = currNode;
            break;
        }
        for (int i = 0; i < V; i++) {
            if (graph[currVertex][i] != INF && currVertex != i) { // 该节点与当前节点相邻且未被访问过
                struct Node childNode;
                childNode.level = currNode.level + 1;
                for (int j = 0; j < V; j++) {
                    childNode.path[j] = currNode.path[j];
                }
                childNode.path[childNode.level] = i;
                childNode.path[childNode.level + 1] = -1;
                childNode.bound = getBound(childNode);
                if (childNode.bound < currNode.bound) { // 可行子节点
                    queue[tail++] = i;
                    currNode = childNode;
                }
            }
        }
    }

    printPath(bestNode.path, V);
    printLength(getBound(bestNode));
}

int main() {
    branchAndBound();
    return 0;
}

在上面的代码示例中，我们使用邻接矩阵来表示图，将图中的边权重存储在一个二维数组中。在`getBound()`函数中，我们计算当前节点的界（上界），以便在后续的搜索中进行剪枝。在`branchAndBound()`函数中，我们使用队列来存储未扩展节点，每次从队列中取出一个节点，然后生成其所有的可行子节点，并计算它们的界。如果可行子节点的界小于当前节点的界，那么就将该子节点加入队列，并更新当前节点为该子节点。当搜索到最后一个节点时，即可输出最短路径及其路径长度。

需要注意的是，分支限界法的时间复杂度较高，当图中节点数较多时，运行时间可能会很长。因此，我们可以在实际应用中根据实际需要选择合适的算法。