无向图最短路径算法 c

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两个结点之间的最短路径。其中一个常用的算法是Dijkstra算法（迪杰斯特拉算法）。该算法的步骤如下：
1. 初始化距离数组D，将起始结点的距离设为0。
2. 创建一个集合S，用来存放已经确定最短路径的结点。
3. 循环n-1次，每次选取一个距离最短且不在集合S中的结点vk，将其加入集合S。
4. 根据条件更新从起始结点到集合S中的所有结点的最短路径长度，即如果存在结点vi，满足D[k] + G.arcs[k][i] < D[i]，则更新D[i] = D[k] + G.arcs[k][i]，同时更新结点vi的前驱为vk。

对于给定的无向图最短路径问题，一种常见的解决方法是将无向图转换为有向图，在有向图上应用Dijkstra算法求解最短路径。转换方法可以是将每条无向边(u, v)转化为有向边(u, v)和(v, u)。然后按照上述步骤执行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)。

无向图 求最短路径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算法，最后输出每个节点到起点的最短路径长度。