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

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

#include <QtDebug>
#include <QMap>
#include <QSet>

// 邻接链表节点
struct AdjListNode {
    int dest;
    int weight;
    AdjListNode* next = nullptr;
};

// 邻接链表
class AdjList {
public:
    AdjListNode* head = nullptr;
};

// 加权有向图
class WeightedGraph {
public:
    QMap<int, AdjList> adjListMap; // 邻接链表映射表

    void addEdge(int src, int dest, int weight) {
        AdjListNode* newNode = new AdjListNode{ dest, weight };
        newNode->next = adjListMap[src].head;
        adjListMap[src].head = newNode;
    }
};

// Dijkstra算法
QMap<int, int> dijkstra(WeightedGraph graph, int src) {
    QMap<int, int> dist; // 源节点到各节点的距离
    QSet<int> visited; // 已访问节点集合
    for (auto key : graph.adjListMap.keys()) {
        dist[key] = INT_MAX; // 初始化距离为无穷大
    }
    dist[src] = 0; // 源节点到自身距离为0

    for (int i = 0; i < graph.adjListMap.size() - 1; i++) {
        int minDist = INT_MAX;
        int minNode = -1;
        // 查找未访问节点中距离最小的节点
        for (auto key : graph.adjListMap.keys()) {
            if (!visited.contains(key) && dist[key] < minDist) {
                minDist = dist[key];
                minNode = key;
            }
        }
        if (minNode == -1) break; // 所有节点均已访问，结束算法

        visited.insert(minNode); // 标记节点为已访问
        // 更新所有邻接节点的距离
        for (auto node = graph.adjListMap[minNode].head; node != nullptr; node = node->next) {
            if (!visited.contains(node->dest) && dist[minNode] != INT_MAX && dist[minNode] + node->weight < dist[node->dest]) {
                dist[node->dest] = dist[minNode] + node->weight;
            }
        }
    }
    return dist;
}

int main() {
    WeightedGraph graph;
    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 7, 8);
    graph.addEdge(1, 2, 8);
    graph.addEdge(1, 7, 11);
    graph.addEdge(2, 3, 7);
    graph.addEdge(2, 8, 2);
    graph.addEdge(2, 5, 4);
    graph.addEdge(3, 4, 9);
    graph.addEdge(3, 5, 14);
    graph.addEdge(4, 5, 10);
    graph.addEdge(5, 6, 2);
    graph.addEdge(6, 7, 1);
    graph.addEdge(6, 8, 6);
    graph.addEdge(7, 8, 7);

    QMap<int, int> dist = dijkstra(graph, 0);
    qDebug() << dist; // 输出：{0=0, 1=4, 2=12, 3=19, 4=21, 5=11, 6=9, 7=8, 8=14}

    return 0;
}

在此示例代码中，我们首先定义了邻接链表节点`AdjListNode`和邻接链表`AdjList`。然后，我们定义了加权有向图`WeightedGraph`，它包含一个邻接链表映射表`adjListMap`，用于存储所有节点的邻接链表。通过`addEdge()`方法，我们可以向图中添加一条从源节点到目标节点的有向边，并指定它的权重。

接下来，我们实现了Dijkstra算法，它接受一个加权有向图和源节点作为参数，并返回一个映射表`dist`，其中包含源节点到所有其他节点的最短距离。在算法中，我们使用了一个未访问节点集合`visited`和一个源节点到各节点的距离映射表`dist`。我们首先将所有节点的距离初始化为无穷大，然后将源节点到自身距离设为0。然后，我们重复以下步骤，直到所有节点均已访问：

1. 在未访问节点中查找距离最小的节点。
2. 标记该节点为已访问。
3. 更新其所有邻接节点的距离。

最后，我们在`main()`函数中创建一个加权有向图，并使用Dijkstra算法计算源节点到所有其他节点的最短距离。最终输出结果为一个映射表，其中键表示节点编号，值表示源节点到该节点的最短距离。