单源最短路径问题用c语言编写程序

单源最短路径问题（Single Source Shortest Path, SSSP）通常是指从图的一个顶点出发找到到其他所有顶点的最短路径。常见的算法有迪杰斯特拉算法（Dijkstra's Algorithm）和贝尔曼-福特算法（Bellman-Ford Algorithm）。这里我将以迪杰斯特拉算法为例，给出一个简单的C语言实现思路。

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

#define V 9 // 图的顶点数

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX;
    int 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 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;

    // 进行V-1次迭代
    for (int count = 0; count < V - 1; count++)
    {
        int u = minDistance(dist, sptSet);

        // 将已访问的节点标记为true
        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];
    }
}

// 主函数，用于测试
int main()
{
    int graph[V][V] = { /* 你的邻接矩阵 */
    // ...
    };

    int src = 0; // 源节点
    dijkstra(graph, src);
    // 输出最短路径信息

    return 0;
}

在这个示例中，`graph[V][V]`是一个二维数组表示邻接矩阵，`dijkstra`函数则是核心部分，实现了迪杰斯特拉算法。记得替换邻接矩阵的内容，并调整`src`变量为你实际的问题需求。