c语言无向图邻接表最短路径

求解无向图邻接表最短路径一般采用 Dijkstra 算法或者 Floyd 算法。

Dijkstra 算法：

1. 初始化一个数组 dis，表示起点到各个顶点的距离，初始值为无穷大，起点到自己的距离为 0。

2. 选择一个起点并将其 dis 值设置为 0。

3. 遍历图中所有顶点，找到当前与起点距离最短的顶点，并将其加入到已经确定最短路径的顶点集合中。

4. 遍历被新加入的顶点所连接的所有边，更新其它顶点到起点的距离 dis。

5. 重复步骤 3 和步骤 4 直到所有顶点都已经确定最短路径。

Floyd 算法：

1. 初始化一个二维数组 dis，表示各个顶点之间的距离。

2. 对于每个顶点，将该顶点到其它顶点的距离存储到 dis 中。

3. 遍历每个顶点，将该顶点作为中转点更新 dis 数组。

4. 重复步骤 3 直到所有顶点都作为中转点更新过。

以上是两种常用的求解无向图邻接表最短路径的算法，你可以根据实际情况选择其中一种进行实现。

相关问题

无向图 求最短路径C语言实现

求无向图的最短路径可以使用Dijkstra算法，其基本思想是从起点开始，每次选择当前最短路径的节点进行扩展，直到扩展到终点或者无法继续扩展为止。

以下是一份C语言实现的示例代码：

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

#define MAX_VERTICES 1000
#define INF INT_MAX

typedef struct {
    int dest;
    int weight;
    struct EdgeNode* next;
} EdgeNode;

typedef struct {
    EdgeNode* head;
} VertexNode;

VertexNode graph[MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];

void addEdge(int src, int dest, int weight) {
    EdgeNode* newNode = (EdgeNode*)malloc(sizeof(EdgeNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = graph[src].head;
    graph[src].head = newNode;
}

int getMinDistVertex(int n) {
    int minDist = INF;
    int minIndex = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < minDist) {
            minDist = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

void dijkstra(int n, int src) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int i = 0; i < n-1; i++) {
        int u = getMinDistVertex(n);
        visited[u] = 1;
        EdgeNode* p = graph[u].head;
        while (p != NULL) {
            int v = p->dest;
            if (!visited[v] && dist[u] != INF && dist[u] + p->weight < dist[v]) {
                dist[v] = dist[u] + p->weight;
            }
            p = p->next;
        }
    }
}

int main() {
    int n, m; // n为节点数，m为边数
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int src, dest, weight;
        scanf("%d%d%d", &src, &dest, &weight);
        addEdge(src, dest, weight);
        addEdge(dest, src, weight);
    }
    dijkstra(n, 0);
    for (int i = 0; i < n; i++) {
        printf("dist[%d] = %d\n", i, dist[i]);
    }
    return 0;
}

其中，`graph`数组用来存储图的邻接表表示，`dist`数组用来存储从起点到每个节点的最短路径长度，`visited`数组用来标记每个节点是否已经被访问过。`addEdge`函数用来添加边，`getMinDistVertex`函数用来获取当前未访问节点中距离起点最近的节点，`dijkstra`函数用来执行Dijkstra算法，最后输出每个节点到起点的最短路径长度。

无向图最短路径c语言代码

以下是使用 Dijkstra 算法求解无向图最短路径的 C 语言代码示例：

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

#define MAX_VERTICES 1000
#define INF INT_MAX

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示图
int dist[MAX_VERTICES];                // 记录每个顶点到源点的最短距离
bool visited[MAX_VERTICES];            // 记录每个顶点是否已被访问

int dijkstra(int n, int s, int t) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[s] = 0;

    // 迭代 n 次
    for (int i = 0; i < n; i++) {
        int u = -1;
        int min_dist = INF;
        // 找到未访问的顶点中距离源点最近的顶点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) break;
        visited[u] = true;

        // 更新 u 的邻居顶点的最短距离
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    return dist[t];
}

int main() {
    // 初始化邻接矩阵
    int n, m; // n 表示顶点个数，m 表示边的条数
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w); // 顶点 u 和顶点 v 之间有一条权值为 w 的边
        graph[u][v] = graph[v][u] = w;
    }

    // 求解最短路径
    int s, t; // 源点 s 和目标点 t
    scanf("%d %d", &s, &t);
    int shortest_dist = dijkstra(n, s, t);
    printf("The shortest path from %d to %d is %d.", s, t, shortest_dist);

    return 0;
}

该代码使用了邻接矩阵表示图，时间复杂度为 O(n^2)。如果使用邻接表表示图，时间复杂度可以优化到 O(ElogV)。