qt用dijkstra算最短路径

QT是一个跨平台的C++应用程序开发框架，可以使用C++编写Dijkstra算法来计算最短路径。

以下是一个简单的Dijkstra算法实现：

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

#define INF INT_MAX

int dijkstra(vector<vector<int>> graph, int start, int end) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> dist(n, INF);
    dist[start] = 0;

    for (int i = 0; i < n - 1; i++) {
        int min_dist = INF;
        int min_index = -1;

        // find the unvisited vertex with smallest distance
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }

        if (min_index == -1) break;

        visited[min_index] = true;

        // update the distances of the adjacent vertices
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[min_index][j] != INF && dist[min_index] + graph[min_index][j] < dist[j]) {
                dist[j] = dist[min_index] + graph[min_index][j];
            }
        }
    }

    return dist[end];
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, INF, 1, 3},
        {2, 0, 4, INF, INF},
        {INF, 4, 0, INF, INF},
        {1, INF, INF, 0, 5},
        {3, INF, INF, 5, 0}
    };

    int start = 0;
    int end = 4;

    int shortest = dijkstra(graph, start, end);

    cout << "The shortest distance from vertex " << start << " to vertex " << end << " is " << shortest << endl;

    return 0;
}

在这个例子中，我们使用一个5x5的邻接矩阵来表示图的连接关系。INF表示两个节点之间没有连接。我们从节点0开始，计算到节点4的最短路径。程序的输出应该是：

The shortest distance from vertex 0 to vertex 4 is 3

这个算法的时间复杂度为O(n^2)，其中n是节点的数量。如果需要更快的算法，可以考虑使用优先队列来实现。