2024-12-27 14:40 已编辑 门头沟学院 C++ 发布于江西
关注
day59
dijkstra（堆优化版）:从边的数量出发，采用邻接表存储图：vector>> grid(n + 1)；
构建小顶堆来直接选最近结点（不需要循环），优先级队列中存放pair<结点编号，结点到起点的距离>，使用vector>作为底层容器,并通过mycomparison类来比较元素；priority_queue, vector>, mycomparison> pq；
时间复杂度：O(ElogE) E 为边的数量
Bellman_ford 算法：求带负权值的单向最短路，dijkstra算法只能求权值为非负数的最短路问题。
思路：对所有边松弛 n-1 次，然后得出得到终点的最短路径。
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，松弛就是一次去获取到该结点的最短路径的尝试，因为给出的边规定了哪个结点到哪个结点有路，这说明某次的松弛操作不一定能真正实行，可能起点到某条边的出发结点还未找到最短路，所以要松弛n-1次，才能最终得到起点到终点的最短路。
// 松弛操作
// minDist[from] != INT_MAX 防止从未计算过的节点出发
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
}
时间复杂度： O(N * E) , N为节点数量，E为图中边的数量
构建小顶堆来直接选最近结点（不需要循环），优先级队列中存放pair<结点编号，结点到起点的距离>，使用vector
时间复杂度：O(ElogE) E 为边的数量
Bellman_ford 算法：求带负权值的单向最短路，dijkstra算法只能求权值为非负数的最短路问题。
思路：对所有边松弛 n-1 次，然后得出得到终点的最短路径。
对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，松弛就是一次去获取到该结点的最短路径的尝试，因为给出的边规定了哪个结点到哪个结点有路，这说明某次的松弛操作不一定能真正实行，可能起点到某条边的出发结点还未找到最短路，所以要松弛n-1次，才能最终得到起点到终点的最短路。
// 松弛操作
// minDist[from] != INT_MAX 防止从未计算过的节点出发
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
}
时间复杂度： O(N * E) , N为节点数量，E为图中边的数量
全部评论
相关推荐
2024-12-27 11:59
门头沟学院 运营 点赞 评论 收藏
分享
点赞 评论 收藏
分享
2024-12-28 12:10
东北林业大学 测试开发 点赞 评论 收藏
分享
查看8道真题和解析