如何用邻接表求最短路径

用邻接表求最短路径一般采用Dijkstra算法。Dijkstra算法是一种贪心算法，它通过维护一个距离起点的距离数组和一个未确定最短路径的节点集合，不断地选择距离起点最近的一个节点，并更新其邻居节点的距离值，直到所有节点都被确定了最短路径为止。

具体实现步骤如下：

1. 初始化距离数组和节点集合，将起点的距离设为0，其余节点的距离设为无穷大，将所有节点加入到未确定最短路径的节点集合中。

2. 不断地从未确定最短路径的节点集合中选择距离起点最近的节点u，并将该节点从集合中删除。

3. 对u的每个邻居节点v，如果从起点到u的距离加上从u到v的距离小于起点到v的距离，则更新起点到v的距离为该值。

4. 重复步骤2和步骤3，直到所有节点都被确定了最短路径为止。

最终，距离数组中存储的就是起点到各个节点的最短距离。可以通过记录每个节点的前驱节点来还原最短路径。

相关问题

给我一个C语言写的用邻接表求最短路径的示例

好的，下面是一个用邻接表求最短路径的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXV 1000
#define INF 0x3f3f3f3f

typedef struct EdgeNode { // 邻接表中边的结构体
    int adjvex; // 邻接顶点编号
    int weight; // 边的权值
    struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;

typedef struct VertexNode { // 邻接表中顶点的结构体
    int data; // 顶点数据
    EdgeNode *firstedge; // 指向第一条边的指针
} VertexNode;

typedef struct Graph { // 邻接表表示的图
    VertexNode vertex[MAXV];
    int n, e; // 顶点数和边数
} Graph;

typedef struct ShortestPath { // 存储最短路径和路径长度
    int path[MAXV];
    int dist[MAXV];
} ShortestPath;

void CreateGraph(Graph *G) { // 创建图
    printf("输入顶点数和边数：");
    scanf("%d %d", &G->n, &G->e);
    printf("输入各顶点的数据：");
    for (int i = 0; i < G->n; i++) {
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].firstedge = NULL;
    }
    for (int i = 0; i < G->e; i++) {
        int u, v, w;
        printf("输入边（u, v）的顶点编号和权值：");
        scanf("%d %d %d", &u, &v, &w);
        EdgeNode *e1 = (EdgeNode *)malloc(sizeof(EdgeNode));
        e1->adjvex = v;
        e1->weight = w;
        e1->next = G->vertex[u].firstedge;
        G->vertex[u].firstedge = e1;
        EdgeNode *e2 = (EdgeNode *)malloc(sizeof(EdgeNode));
        e2->adjvex = u;
        e2->weight = w;
        e2->next = G->vertex[v].firstedge;
        G->vertex[v].firstedge = e2;
    }
}

void Dijkstra(Graph *G, int start, ShortestPath *S) { // Dijkstra算法求最短路径
    int vis[MAXV] = {0}; // 判断该点是否已确定最短路径
    for (int i = 0; i < G->n; i++) {
        S->path[i] = -1; // 初始化路径
        S->dist[i] = INF; // 初始化路径长度
    }
    S->path[start] = start;
    S->dist[start] = 0;
    vis[start] = 1; // 起点已确定最短路径
    EdgeNode *p = G->vertex[start].firstedge;
    while (p) { // 更新起点相邻点的路径长度
        S->dist[p->adjvex] = p->weight;
        S->path[p->adjvex] = start;
        p = p->next;
    }
    for (int i = 1; i < G->n; i++) { // 依次确定剩余的点的最短路径
        int min_dist = INF;
        int u;
        for (int j = 0; j < G->n; j++) { // 找到未确定最短路径的点中距离起点最近的点
            if (!vis[j] && S->dist[j] < min_dist) {
                u = j;
                min_dist = S->dist[j];
            }
        }
        vis[u] = 1;
        p = G->vertex[u].firstedge;
        while (p) { // 更新新确定最短路径的点相邻点的路径长度
            if (!vis[p->adjvex] && S->dist[p->adjvex] > S->dist[u] + p->weight) {
                S->dist[p->adjvex] = S->dist[u] + p->weight;
                S->path[p->adjvex] = u;
            }
            p = p->next;
        }
    }
}

int main() {
    Graph G;
    ShortestPath S;
    CreateGraph(&G);
    Dijkstra(&G, 0, &S);
    printf("最短路径长度：\n");
    for (int i = 0; i < G.n; i++) {
        printf("%d ", S.dist[i]);
    }
    printf("\n最短路径：\n");
    for (int i = 0; i < G.n; i++) {
        printf("%d ", S.path[i]);
    }
    return 0;
}

这个示例程序使用了 Dijkstra 算法求最短路径，实现了一个邻接表表示的图，并且输出了最短路径长度和路径。你可以根据自己的需要修改这个示例程序，来适应你的具体需求。

qt用dijkstra邻接链表算最短路径

以下是使用Dijkstra算法和邻接链表实现最短路径的示例代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> adj[100001]; // 邻接链表
int dist[100001]; // 最短路径长度
bool visited[100001]; // 是否访问过

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));
    dist[start] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u])
            continue;

        visited[u] = true;

        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].to;
            int weight = adj[u][i].weight;

            if (!visited[v] && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n, m, start;
    cin >> n >> m >> start;

    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }

    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(Edge(v, w));
    }

    // 计算最短路径
    dijkstra(start);

    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF)
            cout << "INF" << endl;
        else
            cout << dist[i] << endl;
    }

    return 0;
}

在这个示例代码中，我们使用了邻接链表存储图，并且使用了一个优先队列来实现Dijkstra算法。在计算最短路径时，我们首先将源节点加入优先队列，并将其到源节点的距离设置为0。然后，我们不断取出队列中距离最小的节点，并更新与之相邻的节点的最短路径长度。最终，我们得到了所有节点到源节点的最短路径长度。