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

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

#include <QtDebug>
#include <QVector>
#include <QMap>

//定义邻接链表中的结点
struct Node {
    int index;
    int weight;
    Node(int idx, int wgt): index(idx), weight(wgt) {}
};

//定义邻接链表
typedef QVector<Node> AdjList;
typedef QMap<int, AdjList> Graph;

//Dijkstra算法求解最短路径
void dijkstra(const Graph& graph, int start, QVector<int>& dist, QVector<int>& prev) {
    int n = graph.size();
    QVector<bool> visited(n, false);
    dist.fill(INT_MAX, n);
    dist[start] = 0;
    prev.fill(-1, n);

    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }

        if (dist[u] == INT_MAX) break;

        visited[u] = true;
        const AdjList& adj = graph[u];
        for (int j = 0; j < adj.size(); j++) {
            int v = adj[j].index;
            int w = adj[j].weight;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                prev[v] = u;
            }
        }
    }
}

int main() {
    Graph graph;
    graph[0] = AdjList() << Node(1, 2) << Node(2, 5) << Node(3, 1);
    graph[1] = AdjList() << Node(0, 2) << Node(2, 3) << Node(4, 1);
    graph[2] = AdjList() << Node(0, 5) << Node(1, 3) << Node(3, 2) << Node(4, 5);
    graph[3] = AdjList() << Node(0, 1) << Node(2, 2) << Node(4, 4);
    graph[4] = AdjList() << Node(1, 1) << Node(2, 5) << Node(3, 4);

    QVector<int> dist(graph.size());
    QVector<int> prev(graph.size());
    dijkstra(graph, 0, dist, prev);

    qDebug() << "Shortest path from 0 to 4:";
    for (int i = 4; i != -1; i = prev[i]) {
        qDebug() << i;
    }
    qDebug() << "Shortest distance: " << dist[4];

    return 0;
}

在这个示例中，我们定义了邻接链表的结构体`Node`和类型别名`AdjList`和`Graph`。然后，我们实现了Dijkstra算法的函数`dijkstra`，该函数接受一个邻接链表和一个起点，并计算出从起点到每个顶点的最短距离和最短路径。

最后，我们在`main`函数中创建了一个邻接链表，调用了`dijkstra`函数来计算最短路径和距离，并打印结果。