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

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

首先需要定义一个结构体来表示边：

struct Edge {
    int to; // 边的终点
    int cost; // 边的权值
    Edge(int _to, int _cost) : to(_to), cost(_cost) {}
};

然后定义一个vector数组，每个元素表示一个节点，每个节点包含一个vector<Edge>类型的邻接链表，表示从该节点出发的所有边：

const int INF = 0x3f3f3f3f; // 表示无穷大
vector<Edge> adj[MAX_NODE]; // 邻接链表
int dist[MAX_NODE]; // 存储每个节点到起点的最短距离
bool vis[MAX_NODE]; // 标记每个节点是否被访问过

接下来是Dijkstra算法的核心部分，采用贪心策略，每次找到当前距离起点最近的一个未访问的节点，并更新它的邻居节点的距离：

void dijkstra(int start) {
    memset(vis, false, sizeof(vis)); // 初始化所有节点为未访问
    memset(dist, INF, sizeof(dist)); // 初始化所有节点的距离为无穷大
    dist[start] = 0; // 起点到自身的距离为0
    for (int i = 0; i < MAX_NODE; i++) {
        int u = -1, min_dist = INF; // u表示距离起点最近的未访问节点，min_dist表示当前最短距离
        for (int j = 0; j < MAX_NODE; j++) {
            if (!vis[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) break; // 如果所有节点都已经访问过，结束算法
        vis[u] = true; // 标记节点u为已访问
        for (auto& e : adj[u]) {
            if (vis[e.to]) continue; // 如果节点e.to已经访问过，跳过
            dist[e.to] = min(dist[e.to], dist[u] + e.cost); // 更新到节点e.to的最短距离
        }
    }
}

完整的代码示例：

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

const int INF = 0x3f3f3f3f; // 表示无穷大
const int MAX_NODE = 100; // 最大节点数

struct Edge {
    int to; // 边的终点
    int cost; // 边的权值
    Edge(int _to, int _cost) : to(_to), cost(_cost) {}
};

vector<Edge> adj[MAX_NODE]; // 邻接链表
int dist[MAX_NODE]; // 存储每个节点到起点的最短距离
bool vis[MAX_NODE]; // 标记每个节点是否被访问过

void dijkstra(int start) {
    memset(vis, false, sizeof(vis)); // 初始化所有节点为未访问
    memset(dist, INF, sizeof(dist)); // 初始化所有节点的距离为无穷大
    dist[start] = 0; // 起点到自身的距离为0
    for (int i = 0; i < MAX_NODE; i++) {
        int u = -1, min_dist = INF; // u表示距离起点最近的未访问节点，min_dist表示当前最短距离
        for (int j = 0; j < MAX_NODE; j++) {
            if (!vis[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) break; // 如果所有节点都已经访问过，结束算法
        vis[u] = true; // 标记节点u为已访问
        for (auto& e : adj[u]) {
            if (vis[e.to]) continue; // 如果节点e.to已经访问过，跳过
            dist[e.to] = min(dist[e.to], dist[u] + e.cost); // 更新到节点e.to的最短距离
        }
    }
}

int main() {
    // 添加边
    adj[0].push_back(Edge(1, 2));
    adj[0].push_back(Edge(3, 6));
    adj[1].push_back(Edge(2, 3));
    adj[1].push_back(Edge(3, 8));
    adj[1].push_back(Edge(4, 5));
    adj[2].push_back(Edge(4, 7));
    adj[3].push_back(Edge(4, 9));
    adj[4].push_back(Edge(5, 4));

    dijkstra(0); // 从节点0开始求最短路径

    // 输出每个节点到起点的最短距离
    for (int i = 0; i < MAX_NODE; i++) {
        if (dist[i] == INF) cout << "INF ";
        else cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}