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语言实现该算法的步骤：

1. 首先，我们需要定义一个结构体来表示图中的每个节点，其中包括该节点的编号、到起点的最短距离、以及该节点的前驱节点。

struct Node {
    int id;     // 节点编号
    int dist;   // 到起点的最短距离
    int prev;   // 前驱节点
};

2. 然后，我们需要定义一个函数来读取输入的节点个数和邻接矩阵，并且初始化每个节点的信息。

void init(int n, int matrix[][n], struct Node nodes[]) {
    for (int i = 0; i < n; i++) {
        nodes[i].id = i;
        nodes[i].dist = INT_MAX;    // 初始距离为无穷大
        nodes[i].prev = -1;         // 初始前驱节点为-1
    }
    nodes[0].dist = 0;              // 起点到起点的距离为0

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] != 0) {    // 若节点i和节点j有边相连
                // 将节点i的邻居节点加入节点i的邻接表中
                struct Neighbor *p = (struct Neighbor *) malloc(sizeof(struct Neighbor));
                p->id = j;
                p->weight = matrix[i][j];
                p->next = nodes[i].neighbors;
                nodes[i].neighbors = p;
            }
        }
    }
}

3. 接下来，我们需要定义一个函数来找到当前未访问的节点中距离起点最近的节点。

int find_min_dist(struct Node nodes[], int n) {
    int min_dist = INT_MAX;
    int min_node = -1;
    for (int i = 0; i < n; i++) {
        if (nodes[i].dist < min_dist && nodes[i].visited == 0) {
            min_dist = nodes[i].dist;
            min_node = i;
        }
    }
    return min_node;
}

4. 然后，我们需要定义一个函数来更新当前节点的邻居节点的距离信息。

void update_neighbors(struct Node nodes[], int node_id) {
    struct Neighbor *p = nodes[node_id].neighbors;
    while (p != NULL) {
        int neighbor_id = p->id;
        int new_dist = nodes[node_id].dist + p->weight;
        if (new_dist < nodes[neighbor_id].dist) {
            nodes[neighbor_id].dist = new_dist;
            nodes[neighbor_id].prev = node_id;
        }
        p = p->next;
    }
}

5. 最后，我们可以使用Dijkstra算法来遍历整个图，找到所有节点的最短路径。

void dijkstra(int n, int matrix[][n]) {
    struct Node nodes[n];
    init(n, matrix, nodes);

    int count = 0;
    while (count < n) {
        int node_id = find_min_dist(nodes, n);
        if (node_id == -1) break;
        nodes[node_id].visited = 1;
        update_neighbors(nodes, node_id);
        count++;
    }

    for (int i = 0; i < n; i++) {
        printf("Node %d: dist=%d, prev=%d\n", i, nodes[i].dist, nodes[i].prev);
    }
}

使用以上代码，我们可以输入节点个数和邻接矩阵，然后输出所有节点的最短路径。

用c语言设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： 1． 无向图的基本操作及应用 ① 创建无向图的邻接矩阵 ② 创建无向图的邻接表 ③ 无向图的深度优先遍历 ④ 无向图的广度优先遍历 2． 无向网的基本操作及应用 ① 创建无向网的邻接矩阵 ② 创建无向网的邻接表 ③ 求最小生成树 3． 有向图的基本操作及应用 ① 创建有向图的邻接矩阵 ② 创建有向图的邻接表 ③ 拓扑排序 4． 有向网的基本操作及应用 ① 创建有向网的邻接矩阵 ② 创建有向网的邻接表 ③ 关键路径 ④ 单源最短路径 ⑤ 每对顶点之间的最短路径

以下是一个基于DOS菜单的应用程序设计，可供参考：

#include <stdio.h>
#include <conio.h>

void createUndirectedGraphByMatrix() {
    printf("You have chosen to create an undirected graph by adjacency matrix.\n");
    // TODO: 实现创建无向图邻接矩阵的功能
}

void createUndirectedGraphByList() {
    printf("You have chosen to create an undirected graph by adjacency list.\n");
    // TODO: 实现创建无向图邻接表的功能
}

void traverseUndirectedGraphByDFS() {
    printf("You have chosen to traverse an undirected graph by depth-first search.\n");
    // TODO: 实现无向图深度优先遍历的功能
}

void traverseUndirectedGraphByBFS() {
    printf("You have chosen to traverse an undirected graph by breadth-first search.\n");
    // TODO: 实现无向图广度优先遍历的功能
}

void createUndirectedNetworkByMatrix() {
    printf("You have chosen to create an undirected network by adjacency matrix.\n");
    // TODO: 实现创建无向网邻接矩阵的功能
}

void createUndirectedNetworkByList() {
    printf("You have chosen to create an undirected network by adjacency list.\n");
    // TODO: 实现创建无向网邻接表的功能
}

void findMinimumSpanningTree() {
    printf("You have chosen to find the minimum spanning tree.\n");
    // TODO: 实现求最小生成树的功能
}

void createDirectedGraphByMatrix() {
    printf("You have chosen to create a directed graph by adjacency matrix.\n");
    // TODO: 实现创建有向图邻接矩阵的功能
}

void createDirectedGraphByList() {
    printf("You have chosen to create a directed graph by adjacency list.\n");
    // TODO: 实现创建有向图邻接表的功能
}

void topologicalSort() {
    printf("You have chosen to do a topological sort.\n");
    // TODO: 实现拓扑排序的功能
}

void createDirectedNetworkByMatrix() {
    printf("You have chosen to create a directed network by adjacency matrix.\n");
    // TODO: 实现创建有向网邻接矩阵的功能
}

void createDirectedNetworkByList() {
    printf("You have chosen to create a directed network by adjacency list.\n");
    // TODO: 实现创建有向网邻接表的功能
}

void findCriticalPath() {
    printf("You have chosen to find the critical path.\n");
    // TODO: 实现求关键路径的功能
}

void findShortestPathFromSingleSource() {
    printf("You have chosen to find the shortest path from a single source.\n");
    // TODO: 实现求单源最短路径的功能
}

void findAllPairsShortestPath() {
    printf("You have chosen to find all pairs shortest path.\n");
    // TODO: 实现求每对顶点之间的最短路径的功能
}

int main() {
    int choice1, choice2;

    while (1) {
        printf("Please choose a category:\n");
        printf("1. Undirected Graph\n");
        printf("2. Undirected Network\n");
        printf("3. Directed Graph\n");
        printf("4. Directed Network\n");
        printf("0. Exit\n");

        choice1 = getch() - '0';
        printf("%d\n", choice1);

        if (choice1 == 0) {
            break;
        } else if (choice1 < 1 || choice1 > 4) {
            printf("Invalid choice.\n");
            continue;
        }

        while (1) {
            printf("Please choose a function:\n");

            switch (choice1) {
                case 1:
                    printf("1. Create by adjacency matrix\n");
                    printf("2. Create by adjacency list\n");
                    printf("3. Traverse by depth-first search\n");
                    printf("4. Traverse by breadth-first search\n");
                    break;
                case 2:
                    printf("1. Create by adjacency matrix\n");
                    printf("2. Create by adjacency list\n");
                    printf("3. Find minimum spanning tree\n");
                    break;
                case 3:
                    printf("1. Create by adjacency matrix\n");
                    printf("2. Create by adjacency list\n");
                    printf("3. Topological sort\n");
                    break;
                case 4:
                    printf("1. Create by adjacency matrix\n");
                    printf("2. Create by adjacency list\n");
                    printf("3. Find critical path\n");
                    printf("4. Find shortest path from single source\n");
                    printf("5. Find all pairs shortest path\n");
                    break;
            }

            printf("0. Back\n");

            choice2 = getch() - '0';
            printf("%d\n", choice2);

            if (choice2 == 0) {
                break;
            } else if ((choice1 == 1 && choice2 < 1 || choice2 > 4) ||
                       (choice1 == 2 && choice2 < 1 || choice2 > 3) ||
                       (choice1 == 3 && choice2 < 1 || choice2 > 3) ||
                       (choice1 == 4 && choice2 < 1 || choice2 > 5)) {
                printf("Invalid choice.\n");
                continue;
            }

            switch (choice1) {
                case 1:
                    switch (choice2) {
                        case 1:
                            createUndirectedGraphByMatrix();
                            break;
                        case 2:
                            createUndirectedGraphByList();
                            break;
                        case 3:
                            traverseUndirectedGraphByDFS();
                            break;
                        case 4:
                            traverseUndirectedGraphByBFS();
                            break;
                    }
                    break;
                case 2:
                    switch (choice2) {
                        case 1:
                            createUndirectedNetworkByMatrix();
                            break;
                        case 2:
                            createUndirectedNetworkByList();
                            break;
                        case 3:
                            findMinimumSpanningTree();
                            break;
                    }
                    break;
                case 3:
                    switch (choice2) {
                        case 1:
                            createDirectedGraphByMatrix();
                            break;
                        case 2:
                            createDirectedGraphByList();
                            break;
                        case 3:
                            topologicalSort();
                            break;
                    }
                    break;
                case 4:
                    switch (choice2) {
                        case 1:
                            createDirectedNetworkByMatrix();
                            break;
                        case 2:
                            createDirectedNetworkByList();
                            break;
                        case 3:
                            findCriticalPath();
                            break;
                        case 4:
                            findShortestPathFromSingleSource();
                            break;
                        case 5:
                            findAllPairsShortestPath();
                            break;
                    }
                    break;
            }
        }
    }

    return 0;
}