qt中用dijkstra算法计算最短路径加以注释

// 定义一个结构体，用于存放节点的相关信息
struct Node {
int id; // 节点编号
int dist; // 距离起点的距离
bool visited; // 是否已被访问
vector<int> nexts; // 相邻节点的编号
};

// dijkstra 算法
void dijkstra(vector<Node>& nodes, int start, int end) {
// 初始化节点信息
for (auto& node : nodes) {
node.dist = INT_MAX; // 距离初始化为无穷大
node.visited = false; // 初始时，所有节点均未访问
}
nodes[start].dist = 0; // 起点到起点的距离为0

// 对所有节点进行遍历，找到距离起点最近的节点
for (int i = 0; i < nodes.size(); i++) {
int min_dist = INT_MAX; // 最小距离初始化为无穷大
int min_node = -1; // 最小距离的节点编号初始化为-1

// 遍历所有节点，找到未被访问且距离起点最近的节点
for (int j = 0; j < nodes.size(); j++) {
if (!nodes[j].visited && nodes[j].dist < min_dist) {
min_dist = nodes[j].dist;
min_node = j;
}
}

// 如果没有找到未被访问的节点，则退出循环
if (min_node == -1) {
break;
}

// 将距离起点最近的节点标记为已访问
nodes[min_node].visited = true;

// 更新与该节点相邻节点的距离
for (auto next : nodes[min_node].nexts) {
int dist = nodes[min_node].dist + 1; // 相邻节点到起点的距离为当前节点到起点的距离加1
if (dist < nodes[next].dist) {
nodes[next].dist = dist;
}
}
}

// 输出最短路径的距离
cout << "Shortest distance from " << start << " to " << end << " is " << nodes[end].dist << endl;
}

int main() {
// 构建图的节点信息
vector<Node> nodes(6);
nodes[0].id = 0;
nodes[0].nexts.push_back(1);
nodes[0].nexts.push_back(2);
nodes[1].id = 1;
nodes[1].nexts.push_back(0);
nodes[1].nexts.push_back(3);
nodes[2].id = 2;
nodes[2].nexts.push_back(0);
nodes[2].nexts.push_back(3);
nodes[3].id = 3;
nodes[3].nexts.push_back(1);
nodes[3].nexts.push_back(2);
nodes[3].nexts.push_back(4);
nodes[4].id = 4;
nodes[4].nexts.push_back(3);
nodes[4].nexts.push_back(5);
nodes[5].id = 5;
nodes[5].nexts.push_back(4);

// 计算最短路径
dijkstra(nodes, 0, 5);

return 0;
}