数据结构与算法7-9(旅游规划）问题的求解（2）


Dijkstra算法的执行步骤如下：

1.初始化：选择一个起点，将其加入已求出最短路径的集合S中，其余顶点放入未求出最短路径的集合U中。起点到自身的距离为0，到其他点的距离初始化为无穷大。

2.选择和更新：从集合U中选出距离起点最近的顶点K，将其加入集合S，并从集合U中移除。更新集合U中各顶点到起点的距离。

3.重复操作：重复第2步，直到遍历完所有顶点

代码实现如下：
// 优先队列用于Dijkstra算法，按照路径长度排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(n, INF); // 存储到每个城市的最短路径长度
vector<int> cost(n, INF); // 存储到每个城市的最小费用

pq.push({ 0, s }); // 起始城市，路径长度为0
dist[s] = 0;
cost[s] = 0;

while (!pq.empty()) {
int u = pq.top().second;
pq.pop();

for (const Edge& e : graph[u]) {
int v = e.to;
int length = e.length;
int c = e.cost;

// 如果找到更短的路径或者同样长度但费用更低的路径
if (dist[u] + length < dist[v] || (dist[u] + length == dist[v] && cost[u] + c < cost[v])) {
dist[v] = dist[u] + length;
cost[v] = cost[u] + c;
pq.push({ dist[v], v });
}
}
}

展示运行的结果：