C语言找无向图图的最长路径算法代码

在C语言中，寻找无向图的最长路径通常使用Dijkstra算法或者Floyd-Warshall算法。这里以Dijkstra算法为例，因为它更适合求单源最短路径，而无向图的最长路径问题可以转化为从图的一个顶点开始，找到所有其他顶点到起点的最短路径。

以下是Dijkstra算法的基本步骤：

1. 初始化：将起始节点的距离设为0，其余所有节点距离设为无穷大，标记为未访问（未处理）。
2. 选择最小距离的节点：从未访问节点中选择距离起点最近的那个节点。
3. 更新邻居节点：对于当前节点的所有邻居，如果通过该节点到达它们的距离比已知的距离更小，更新其距离。
4. 标记节点：将当前节点标记为已访问。
5. 重复步骤2-4，直到所有节点都被访问过或者找到了最长路径。

由于代码较长，这里给出一个简化的伪代码版本：

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

#define V 9 // 图的顶点数

void dijkstra(int graph[V][V], int src) {
    int dist[V]; // 存储每个节点到src的最短距离
    bool visited[V]; // 标记节点是否已被访问

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = findMinDistance(dist, visited);
        visited[u] = true;

        // 更新u的所有邻接节点的距离
        for (int v = 0; v < V; v++)
            if (!visited[v] && graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printf("Length of the longest path from %d is: %d\n", src, dist[V - 1]);
}

// 辅助函数：查找最小距离的节点
int findMinDistance(int dist[], bool visited[]) {
    int minDist = INT_MAX, minIndex = -1;
    for (int v = 0; v < V; v++)
        if (!visited[v] && dist[v] <= minDist)
            minDist = dist[v], minIndex = v;
    return minIndex;
}

int main() {
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                        {4, 0, 8, 0, 0, 0, 0, 11, 0},
                        {0, 8, 0, 7, 0, 4, 0, 0, 2},
                        {0, 0, 7, 0, 9, 14, 0, 0, 0},
                        {0, 0, 0, 9, 0, 10, 0, 0, 0},
                        {0, 0, 4, 14, 10, 0, 2, 0, 0},
                        {0, 0, 0, 0, 0, 2, 0, 1, 6},
                        {8, 11, 0, 0, 0, 0, 1, 0, 7},
                        {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    dijkstra(graph, 0); // 以节点0作为源节点运行Dijkstra
    return 0;
}