单源最短路径问题用分支限界法用c语言编写程序

单源最短路径问题是图论中的经典问题，其中我们寻找从给定起点到图中所有其他节点的最短路径。分支限界算法是一种搜索策略，常用于解决这类组合优化问题。以下是使用C语言实现Dijkstra算法（一种常见的求解单源最短路径问题的方法），它属于广度优先搜索的一种变体：

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

#define V 9 // 定义图的最大顶点数

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void printSolution(int dist[])
{
    printf("Vertex\t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src)
{
    int dist[V]; // 存储最短距离
    bool sptSet[V]; // 标记是否找到最短路径

    // 初始化所有顶点的距离为无穷大
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    // 设置源节点的距离为0
    dist[src] = 0;

    // 通过迭代将邻接顶点的距离更新为已知的最短路径
    for (int count = 0; count < V - 1; ) {
        // 找出未标记的最小距离节点
        int u = minDistance(dist, sptSet);

        // 将该节点标记为已处理
        sptSet[u] = true;

        // 更新其相邻节点的距离
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];

        count++;
    }

    printSolution(dist);
}

// 主函数，传入图和源节点
int main()
{
    int graph[V][V] = { /* 图的邻接矩阵，填充实际值 */ };
    int source = 0; // 示例，替换为你想要找最短路径的起始节点

    dijkstra(graph, source);

    return 0;
}

在这个例子中，`graph[V][V]` 是一个二维数组，表示图的邻接矩阵。你可以根据需要修改这个矩阵来表示你的图结构。运行这段代码后，会输出从指定源节点到所有其他节点的最短路径。