qt写dijkstra算法
时间: 2023-10-14 08:06:04 浏览: 184
以下是使用Qt实现Dijkstra算法的示例代码。该代码使用了QMap和QSet来存储节点和边,以及使用了QQueue来实现广度优先搜索。
```
#include <QtCore/QCoreApplication>
#include <QMap>
#include <QSet>
#include <QPair>
#include <QQueue>
#include <QDebug>
typedef QPair<int, int> Edge;
typedef QMap<int, QSet<Edge> > Graph;
void dijkstra(const Graph& graph, int start, int end)
{
QMap<int, int> distances;
QMap<int, int> previous;
QSet<int> unvisited;
// 初始化距离和前驱节点
foreach (int node, graph.keys()) {
distances[node] = INT_MAX;
previous[node] = -1;
unvisited.insert(node);
}
distances[start] = 0;
while (!unvisited.isEmpty()) {
// 选择距离最小的节点
int current = -1;
int minDist = INT_MAX;
foreach (int node, unvisited) {
if (distances[node] < minDist) {
current = node;
minDist = distances[node];
}
}
// 如果到终点的距离已知,就可以提前结束
if (current == end) {
break;
}
unvisited.remove(current);
// 更新相邻节点的距离
foreach (const Edge& edge, graph[current]) {
int neighbor = edge.first;
int distance = edge.second;
int alt = distances[current] + distance;
if (alt < distances[neighbor]) {
distances[neighbor] = alt;
previous[neighbor] = current;
}
}
}
// 打印最短路径
QList<int> path;
for (int node = end; node != -1; node = previous[node]) {
path.prepend(node);
}
qDebug() << "Shortest path from" << start << "to" << end << ":";
qDebug() << " Distance:" << distances[end];
qDebug() << " Path:" << path;
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
Graph graph;
graph[0].insert(Edge(1, 7));
graph[0].insert(Edge(2, 9));
graph[0].insert(Edge(5, 14));
graph[1].insert(Edge(2, 10));
graph[1].insert(Edge(3, 15));
graph[2].insert(Edge(3, 11));
graph[2].insert(Edge(5, 2));
graph[3].insert(Edge(4, 6));
graph[4].insert(Edge(5, 9));
dijkstra(graph, 0, 4);
return a.exec();
}
```
阅读全文