qt用dijkstra计算最短路径

在Qt中使用Dijkstra算法计算最短路径可以按照以下步骤：

1. 定义图的数据结构：通常使用邻接矩阵或邻接表来表示图，这里以邻接表为例。定义一个结构体表示每个节点，其中包含节点编号、节点到源节点的距离和前驱节点等信息。定义一个vector表示整个图。

struct Node{
    int id; //节点编号
    int distance; //到源节点的距离
    int preNode; //前驱节点
    vector<pair<int,int>> edges; //邻接边
};
vector<Node> graph; //表示整个图

2. 初始化图：根据实际情况添加节点和边。

void initGraph(){
    //添加节点
    Node node1 = {0,0,-1,{{1,4},{2,2}}};
    Node node2 = {1,INF,-1,{{3,3},{4,1}}};
    Node node3 = {2,INF,-1,{{3,5},{4,6}}};
    Node node4 = {3,INF,-1,{{5,5}}};
    Node node5 = {4,INF,-1,{{5,8}}};
    Node node6 = {5,INF,-1,{}};
    graph.push_back(node1);
    graph.push_back(node2);
    graph.push_back(node3);
    graph.push_back(node4);
    graph.push_back(node5);
    graph.push_back(node6);
}

3. 实现Dijkstra算法：使用一个set来存储还未确定最短路径的节点，每次从set中取出距离源节点最近的节点，更新其相邻节点的距离和前驱节点，再将其从set中删除。重复此过程直到set为空。

void dijkstra(int start){
    set<pair<int,int>> s; //存储还未确定最短路径的节点
    for(int i=0;i<graph.size();i++){
        if(i!=start) graph[i].distance = INF; //初始化距离为无穷大
        s.insert({graph[i].distance,i});
    }
    while(!s.empty()){
        auto it = s.begin();
        int curNode = it->second;
        s.erase(it);
        for(auto edge:graph[curNode].edges){
            int nextNode = edge.first;
            int weight = edge.second;
            if(graph[curNode].distance+weight<graph[nextNode].distance){
                s.erase({graph[nextNode].distance,nextNode});
                graph[nextNode].distance = graph[curNode].distance+weight;
                graph[nextNode].preNode = curNode;
                s.insert({graph[nextNode].distance,nextNode});
            }
        }
    }
}

4. 调用Dijkstra算法并输出结果：传入源节点编号，调用Dijkstra算法计算最短路径，输出每个节点到源节点的距离和前驱节点。

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    initGraph();
    dijkstra(0);

    for(int i=0;i<graph.size();i++){
        cout<<"Node "<<graph[i].id<<": ";
        if(graph[i].distance==INF){
            cout<<"No path."<<endl;
            continue;
        }
        cout<<graph[i].distance<<" (";
        int preNode = graph[i].preNode;
        while(preNode!=-1){
            cout<<preNode<<" ";
            preNode = graph[preNode].preNode;
        }
        cout<<")"<<endl;
    }

    return a.exec();
}

输出结果如下：

Node 0: 0 ()
Node 1: 4 (0 )
Node 2: 2 (0 )
Node 3: 7 (1 2 )
Node 4: 5 (2 )
Node 5: 13 (4 3 )