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

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

首先，我们需要定义一个节点类，用于表示图中的每个节点：

class Node {
public:
    int id; // 节点的编号
    QList<QPair<int, int>> edges; // 与该节点相邻的边，每个边包含相邻节点的编号和边的权值
    int distance; // 节点到起点的距离
    bool visited; // 节点是否已经被访问过

    Node(int id) {
        this->id = id;
        this->distance = INT_MAX;
        this->visited = false;
    }
};

然后，我们需要定义一个图类，用于存储所有的节点，并实现Dijkstra算法：

class Graph {
public:
    QMap<int, Node*> nodes; // 所有的节点
    QList<int> shortestPath(int startId, int endId); // 计算从起点到终点的最短路径
};

QList<int> Graph::shortestPath(int startId, int endId) {
    // 初始化各个节点的距离和访问状态
    for (auto node : nodes.values()) {
        node->distance = INT_MAX;
        node->visited = false;
    }

    // 设置起点的距离为0
    nodes[startId]->distance = 0;

    // 用一个优先队列来存储所有未访问的节点，以距离为键值
    QPriorityQueue<QPair<int, Node*>> queue;
    queue.enqueue({0, nodes[startId]});

    // 开始Dijkstra算法
    while (!queue.isEmpty()) {
        // 取出当前距离最短的节点
        Node* current = queue.dequeue().second;

        if (current->visited) {
            // 如果该节点已经被访问过，则跳过
            continue;
        }

        current->visited = true;

        // 更新与该节点相邻的节点的距离
        for (auto edge : current->edges) {
            int neighborId = edge.first;
            int distance = edge.second;

            Node* neighbor = nodes[neighborId];

            if (!neighbor->visited && current->distance + distance < neighbor->distance) {
                neighbor->distance = current->distance + distance;
                queue.enqueue({neighbor->distance, neighbor});
            }
        }
    }

    // 计算最短路径
    QList<int> path;
    Node* current = nodes[endId];

    while (current != nullptr) {
        path.prepend(current->id);
        current = current->distance == INT_MAX ? nullptr : nodes[current->previous];
    }

    return path;
}

最后，我们可以在Qt中使用这个图类来计算最短路径：

Graph graph;

// 添加所有的节点和边
// ...

// 计算从节点1到节点10的最短路径
QList<int> path = graph.shortestPath(1, 10);

// 输出最短路径
qDebug() << "Shortest path: " << path;