qt实现dijkstra算法

以下是使用Qt实现Dijkstra算法的示例代码：

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

class Graph
{
public:
    Graph();
    void addEdge(QString from, QString to, int weight);
    QMap<QString, int> dijkstra(QString startNode);

private:
    QMap<QString, QMap<QString, int>> m_adjacencyList;
};

Graph::Graph() {}

void Graph::addEdge(QString from, QString to, int weight)
{
    if (!m_adjacencyList.contains(from)) {
        m_adjacencyList[from] = QMap<QString, int>();
    }
    m_adjacencyList[from][to] = weight;
}

QMap<QString, int> Graph::dijkstra(QString startNode)
{
    QMap<QString, int> distance;
    QList<QString> unvisitedNodes;

    // Initialize distance values and unvisited nodes.
    for (auto node : m_adjacencyList.keys()) {
        distance[node] = INT_MAX;
        unvisitedNodes.append(node);
    }
    distance[startNode] = 0;

    while (!unvisitedNodes.isEmpty()) {
        // Find node with minimum distance value.
        int minDistance = INT_MAX;
        QString currentNode;
        for (auto node : unvisitedNodes) {
            if (distance[node] < minDistance) {
                minDistance = distance[node];
                currentNode = node;
            }
        }

        // Update distance values of adjacent nodes.
        for (auto neighbor : m_adjacencyList[currentNode].keys()) {
            int newDistance = distance[currentNode] + m_adjacencyList[currentNode][neighbor];
            if (newDistance < distance[neighbor]) {
                distance[neighbor] = newDistance;
            }
        }

        // Remove current node from unvisited nodes.
        unvisitedNodes.removeOne(currentNode);
    }

    return distance;
}

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

    // Create graph.
    Graph graph;
    graph.addEdge("A", "B", 2);
    graph.addEdge("A", "C", 4);
    graph.addEdge("B", "C", 1);
    graph.addEdge("B", "D", 7);
    graph.addEdge("C", "D", 3);

    // Run Dijkstra's algorithm.
    QMap<QString, int> distances = graph.dijkstra("A");

    // Print distances from start node.
    for (auto node : distances.keys()) {
        qDebug() << node << ": " << distances[node];
    }

    return a.exec();
}

这个示例代码创建了一个简单的有向加权图，其中节点有A、B、C和D，边有AB、AC、BC、BD和CD。然后，它运行Dijkstra算法来计算从起始节点A到每个节点的最短距离，并打印结果。

注意：这个示例代码假设所有边的权重都是正整数。如果有负权重，需要使用Bellman-Ford算法。