qt中dijkstra算法计算最短路径

在Qt中实现Dijkstra算法计算最短路径，需要按照以下步骤进行：

1. 定义节点类和边类，分别表示图中的节点和边，其中节点类需要包含节点编号、节点名称、与该节点相邻的边等属性，边类需要包含边的起点、终点、边权值等属性。

2. 定义图类，表示整个图，包含节点集合和边集合等属性，以及添加节点和边的方法。

3. 实现Dijkstra算法，主要包括以下步骤：

a. 初始化：将起点距离设置为0，其他节点距离设置为无穷大，将所有节点加入未确定集合。

b. 循环处理：从未确定集合中选取距离起点最短的节点作为当前节点，将其标记为已确定，并更新其相邻节点的距离值。

c. 更新相邻节点的距离值：如果当前节点到相邻节点的距离小于相邻节点的原距离，则更新相邻节点的距离值。

4. 最后，输出起点到各个节点的最短距离即可。

下面是一个简单的示例：

// 节点类
class Node {
public:
    int id; // 节点编号
    QString name; // 节点名称
    QList<Edge*> edges; // 与该节点相邻的边

    int dist; // 距离起点的距离
    bool visited; // 是否已确定
    Node* prev; // 前驱节点

    Node(int id, const QString& name) : id(id), name(name), dist(INT_MAX), visited(false), prev(nullptr) {}
};

// 边类
class Edge {
public:
    Node* from; // 起点
    Node* to; // 终点
    int weight; // 边权值

    Edge(Node* from, Node* to, int weight) : from(from), to(to), weight(weight) {}
};

// 图类
class Graph {
public:
    QList<Node*> nodes; // 节点集合
    QList<Edge*> edges; // 边集合

    void addNode(Node* node) {
        nodes.append(node);
    }

    void addEdge(Edge* edge) {
        edges.append(edge);
        edge->from->edges.append(edge);
    }
};

// 实现Dijkstra算法
void dijkstra(Graph* graph, Node* start) {
    start->dist = 0; // 起点距离为0

    QList<Node*> unsetNodes = graph->nodes; // 未确定集合
    while (!unsetNodes.isEmpty()) {
        // 选取距离起点最短的节点
        Node* curNode = nullptr;
        int curDist = INT_MAX;
        foreach (Node* node, unsetNodes) {
            if (node->dist < curDist) {
                curNode = node;
                curDist = node->dist;
            }
        }

        if (curNode == nullptr) {
            break; // 所有节点已确定
        }

        curNode->visited = true; // 标记为已确定
        unsetNodes.removeOne(curNode);

        // 更新相邻节点的距离值
        foreach (Edge* edge, curNode->edges) {
            Node* adjNode = edge->to;
            if (!adjNode->visited) {
                int newDist = curDist + edge->weight;
                if (newDist < adjNode->dist) {
                    adjNode->dist = newDist;
                    adjNode->prev = curNode;
                }
            }
        }
    }
}

// 输出最短路径
void printShortestPaths(Node* start) {
    foreach (Node* node, start->graph->nodes) {
        qDebug() << QString("Shortest path to %1: %2").arg(node->name).arg(node->dist);
    }
}

// 示例代码
Graph* graph = new Graph;

Node* a = new Node(1, "A");
Node* b = new Node(2, "B");
Node* c = new Node(3, "C");
Node* d = new Node(4, "D");
Node* e = new Node(5, "E");

graph->addNode(a);
graph->addNode(b);
graph->addNode(c);
graph->addNode(d);
graph->addNode(e);

graph->addEdge(new Edge(a, b, 10));
graph->addEdge(new Edge(a, c, 20));
graph->addEdge(new Edge(b, c, 30));
graph->addEdge(new Edge(b, d, 5));
graph->addEdge(new Edge(c, b, 40));
graph->addEdge(new Edge(c, d, 15));
graph->addEdge(new Edge(c, e, 20));
graph->addEdge(new Edge(d, e, 10));

a->graph = graph;

dijkstra(graph, a);

printShortestPaths(a);