电子商务网站建设 期末考试试卷以及答案,昆山新宇网站建设,番禺五屏网站建设,DS716 II 做网站数据结构、算法总述#xff1a;数据结构/算法 C/C-CSDN博客 目录
朴素dijkstra算法
堆优化版dijkstra算法
Bellman-Ford算法
spfa 算法#xff08;队列优化的Bellman-Ford算法#xff09;
spfa判断图中是否存在负环
floyd算法 朴素dijkstra算法
思路#xff1a; 集合…数据结构、算法总述数据结构/算法 C/C-CSDN博客 目录
朴素dijkstra算法
堆优化版dijkstra算法
Bellman-Ford算法
spfa 算法队列优化的Bellman-Ford算法
spfa判断图中是否存在负环
floyd算法 朴素dijkstra算法
思路 集合S为已经确定最短路径的点集。 初始化距离 一号结点的距离为零其他结点的距离设为无穷大。循环n次每一次将集合S之外距离最短X的点加入到S中去这里的距离最短指的是距离1号点最近。点X的路径一定最短基于贪心。然后用点X更新X邻接点的距离。 int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路如果不存在则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i n - 1; i ){int t -1; // 在还未确定最短路的点中寻找距离最小的点for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;// 用t更新其他点的距离for (int j 1; j n; j )dist[j] min(dist[j], dist[t] g[t][j]);st[t] true;}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}
题目
849. Dijkstra求最短路 I - AcWing题库https://www.acwing.com/problem/content/description/851/
堆优化版dijkstra算法
思路 一号点的距离初始化为零其他点初始化成无穷大。将一号点放入堆中。不断循环直到堆空。每一次循环中执行的操作为 弹出堆顶与朴素版diijkstra找到S外距离最短的点相同并标记该点的最短路径已经确定。 用该点更新临界点的距离若更新成功就加入到堆中。 typedef pairint, int PII;int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定// 求1号点到n号点的最短距离如果不存在则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;priority_queuePII, vectorPII, greaterPII heap;heap.push({0, 1}); // first存储距离second存储节点编号while (heap.size()){auto t heap.top();heap.pop();int ver t.second, distance t.first;if (st[ver]) continue;st[ver] true;for (int i h[ver]; i ! -1; i ne[i]){int j e[i];if (dist[j] distance w[i]){dist[j] distance w[i];heap.push({dist[j], j});}}}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}
题目
850. Dijkstra求最短路 II - AcWing题库https://www.acwing.com/problem/content/852/
Bellman-Ford算法
Bellman - ford 算法是求含负权图的单源最短路径的一种算法效率较低代码难度较小。其原理为连续进行松弛在每次松弛时把每条边都更新一下若在 n-1 次松弛后还能更新则说明图中有负环因此无法得出结果否则就完成。 (通俗的来讲就是假设 1 号点到 n 号点是可达的每一个点同时向指向的方向出发更新相邻的点的最短距离通过循环 n-1 次操作若图中不存在负环则 1 号点一定会到达 n 号点若图中存在负环则在 n-1 次松弛后一定还会更新)
松弛操作对于图中的每一条边如果通过这条边可以使得达到某个顶点的距离更短则更新这个顶点的最短路径估计值和前驱节点。
步骤 for n次 for 所有边 a,b,w (松弛操作) dist[b] min(dist[b],back[a] w) 注意back[] 数组是上一次迭代后 dist[] 数组的备份由于是每个点同时向外出发因此需要对 dist[] 数组进行备份若不进行备份会因此发生串联效应影响到下一个点 int n, m; // n表示点数m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离struct Edge // 边a表示出点b表示入点w表示边的权重
{int a, b, w;
}edges[M];// 求1到n的最短路距离如果无法从1走到n则返回-1。
int bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;// 如果第n次迭代仍然会松弛三角不等式就说明存在一条长度是n1的最短路径由抽屉原理路径中至少存在两个相同的点说明图中存在负权回路。for (int i 0; i n; i ){for (int j 0; j m; j ){int a edges[j].a, b edges[j].b, w edges[j].w;if (dist[b] dist[a] w)dist[b] dist[a] w;}}if (dist[n] 0x3f3f3f3f / 2) return -1;return dist[n];
}
题目
AcWing 853. 有边数限制的最短路 - AcWinghttps://www.acwing.com/activity/content/problem/content/922/
spfa 算法队列优化的Bellman-Ford算法
步骤 初始化与Bellman-Ford算法相同将所有节点的最短路径估计值设置为无穷大只将源点设为0。创建一个队列并将源点加入队列。当队列非空时进行以下操作 从队列中取出一个顶点u。 对于从顶点u出发的每一条边u-v如果通过这条边可以使得达到顶点v的距离更短则更新顶点v的最短路径估计值和前驱节点并将顶点v加入队列。重复步骤3直到队列为空。如果在队列为空之后再次对所有的边进行一次松弛操作如果还能继续松弛说明图中存在负权回路。 int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中// 求1号点到n号点的最短路距离如果从1号点无法走到n号点则返回-1
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;queueint q;q.push(1);st[1] true;while (q.size()){auto t q.front();q.pop();st[t] false;for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (dist[j] dist[t] w[i]){dist[j] dist[t] w[i];if (!st[j]) // 如果队列中已存在j则不需要将j重复插入{q.push(j);st[j] true;}}}}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}
题目
851. spfa求最短路 - AcWing题库https://www.acwing.com/problem/content/853/
spfa判断负环
什么时候出现负环 在求从1到x的最短路中最多有n - 1条边也就是历经n个点如果中间出现n条边的话 就会出现负环根据抽屉原理 抽屉原理如果每个抽屉代表一个集合每一个苹果就可以代表一个元素假如有n1个元素放到n个集合中去其中必定有一个集合里至少有两个元素。 维护cnt数组的作用 记录每个点到起点的边数当cnt[i] n 表示出现了边数结点数必然有环而且一定是负环 int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中// 如果存在负环则返回true否则返回false。
bool spfa()
{// 不需要初始化dist数组// 原理如果某条最短路径上有n个点除了自己那么加上自己之后一共有n1个点由抽屉原理一定有两个点相同所以存在环。queueint q;for (int i 1; i n; i ){q.push(i);st[i] true;}while (q.size()){auto t q.front();q.pop();st[t] false;for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (dist[j] dist[t] w[i]){dist[j] dist[t] w[i];cnt[j] cnt[t] 1;if (cnt[j] n) return true; // 如果从1号点到x的最短路中包含至少n个点不包括自己则说明存在环if (!st[j]){q.push(j);st[j] true;}}}}return false;
}
题目
852. spfa判断负环 - AcWing题库https://www.acwing.com/problem/content/854/
floyd算法
Floyd-Warshall算法的核心思想是逐步推算出任意两个顶点之间的最短路径。算法首先假设所有顶点对之间的路径长度都是无穷大然后逐步更新这些长度值直到找到所有顶点对之间的最短路径。
初始化for (int i 1; i n; i )for (int j 1; j n; j )if (i j) d[i][j] 0;else d[i][j] INF;// 算法结束后d[a][b]表示a到b的最短距离
void floyd()
{for (int k 1; k n; k )for (int i 1; i n; i )for (int j 1; j n; j )d[i][j] min(d[i][j], d[i][k] d[k][j]);
}
题目
854. Floyd求最短路 - AcWing题库https://www.acwing.com/problem/content/856/
