用c语言求无向网中起点到终点的最短路径

求无向网中起点到终点的最短路径可以使用Dijkstra算法。

首先，需要定义一个结构体表示图中的一条边，包括起点、终点和边权值：

typedef struct {
    int start;  // 边的起点
    int end;    // 边的终点
    int weight; // 边的权值
} Edge;

接下来，可以定义一个二维数组`graph`表示图中各个节点之间的边权值，如果两个节点之间没有边，则边权值为无穷大。

#define INF 0x3f3f3f3f // 表示无穷大

int graph[MAX_NODE][MAX_NODE]; // 图的邻接矩阵表示

然后，就可以使用Dijkstra算法求解起点到终点的最短路径了。具体步骤如下：

1. 初始化距离数组`dist`和标记数组`visited`，将起点的距离设为0，其他节点的距离设为无穷大，标记数组初始全部为false。

int dist[MAX_NODE];    // 起点到各个节点的距离
bool visited[MAX_NODE]; // 标记数组，表示节点是否已经访问过

void dijkstra(int start, int end, int n) {
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; i++) {
        dist[i] = graph[start][i];
    }
    dist[start] = 0;
}

2. 从未标记的节点中选择距离起点最近的节点，并标记为已访问。

int min_dist = INF;
int u = start;

for (int i = 0; i < n; i++) {
    if (!visited[i] && dist[i] < min_dist) {
        min_dist = dist[i];
        u = i;
    }
}

visited[u] = true;

3. 更新起点到相邻节点的距离，如果距离更小则更新距离数组`dist`。

for (int v = 0; v < n; v++) {
    if (!visited[v] && graph[u][v] != INF) {
        if (dist[u] + graph[u][v] < dist[v]) {
            dist[v] = dist[u] + graph[u][v];
        }
    }
}

4. 重复步骤2和3，直到终点被标记为已访问或者所有未标记节点的距离为无穷大。

while (!visited[end]) {
    // 选择距离起点最近的节点
    int min_dist = INF;
    int u = start;

    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < min_dist) {
            min_dist = dist[i];
            u = i;
        }
    }

    visited[u] = true;

    // 更新起点到相邻节点的距离
    for (int v = 0; v < n; v++) {
        if (!visited[v] && graph[u][v] != INF) {
            if (dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
}

完整代码如下：