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

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

#include <QtCore/QCoreApplication>
#include <QtCore/QDebug>

#include <vector>
#include <list>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

class Edge {
public:
    int to;
    int weight;

    Edge(int to, int weight) : to(to), weight(weight) {}
};

typedef list<Edge> EdgeList;
typedef vector<EdgeList> AdjList;

void dijkstra(const AdjList& graph, int start, vector<int>& dist, vector<int>& prev)
{
    int n = graph.size();
    dist.assign(n, INF);
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(dist[start], start));

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        for (auto& e : graph[u]) {
            int v = e.to;
            int w = e.weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                q.push(make_pair(dist[v], v));
            }
        }
    }
}

void printPath(const vector<int>& prev, int u)
{
    if (prev[u] != -1) {
        printPath(prev, prev[u]);
    }
    qDebug() << u;
}

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

    AdjList graph(5);

    graph[0].push_back(Edge(1, 10));
    graph[0].push_back(Edge(2, 3));
    graph[1].push_back(Edge(2, 1));
    graph[1].push_back(Edge(3, 2));
    graph[2].push_back(Edge(1, 4));
    graph[2].push_back(Edge(3, 8));
    graph[2].push_back(Edge(4, 2));
    graph[3].push_back(Edge(4, 7));
    graph[4].push_back(Edge(3, 9));

    vector<int> dist(5);
    vector<int> prev(5, -1);

    dijkstra(graph, 0, dist, prev);

    printPath(prev, 4);

    return a.exec();
}

这个代码使用了C++11的一些特性，如auto和lambda表达式。需要使用C++11以上的编译器才能编译通过。