网站建设方案书备案,wordpress版权加密,加强专业建设的主要举措,分类信息导航网站模板例题地址
多源最短路径
多个源点多个终点可以使用Floyd算法直接求各源点到终点的最短距离#xff0c;也可以直接多次使用dijsktra算法求单源点到终点的最短距离
Floyd算法
使用条件
多源最短路径权值正负皆可
核心思想#xff1a;动态规划
子问题#xff1a; 设(A,B)…例题地址
多源最短路径
多个源点多个终点可以使用Floyd算法直接求各源点到终点的最短距离也可以直接多次使用dijsktra算法求单源点到终点的最短距离
Floyd算法
使用条件
多源最短路径权值正负皆可
核心思想动态规划
子问题 设(A,B)表示顶点A,B之间的距离则有可能(A,B)(A,C)(C,B)这说明AB之间的距离可以继续分解为AC,CB之间的距离问题我们可以找到一个子问题而这就体现了动态规划的思想 定义dp数组 因为从存储上来讲我们需要利用邻接矩阵所以AB间的最短距离表示至少需要两个维度i和j所以dp数组至少有两个维度。又因为从子问题的角度我们分解问题的出发点是找一个中间结点比较AB的最短距离经过中间结点C会不会更短。所以定义一个新的维度k其含义是考虑下标从1开始到k结束的k个顶点是否应该加入到路径中去。(这个定义有鲜明的dp特色,学过dp应该不难理解) 因此dp数组的定义如下dp[i][j][k]表示考虑下标1~k的k个顶点的 i到j的最短距离 递推公式 根据定义不难想到递推公式就是是否应该将下标为k的结点是否值得加入到路径中去不加入k结点dp[i][j][k - 1] (言外之意就是i和j已经连通加入k结点不值得)加入k结点dp[i][k][k - 1] dp[k][j][k - 1]完整公式dp[i][j][k] min(dp[i][j][k - 1], dp[i][k][k - 1] dp[k][j][k - 1]); 初始化 处理输入时要考虑k这个维度应该怎么设置。一种简单的想法是把k设置无关紧要或者无意义的数值(根据不同题目需要可能是INT_MAX/INT_MIN/0)这里设置为0 dp[u][v][0] w; 遍历顺序 其实这个很简单根据递推公式dp[i][j][k-1]中k-1个维度的数据必须知道否则会造成无意义的更新所以k必须在外层循环
个人代码
using namespace std;
using ll long long;
int n, m, u, v, w,q,start,ed;
void solve() {cin n m;vector vectorvectorintdp(n 1, vectorvectorint(n 1, vectorint(n 1, 10009)));//dp数组while (m--) {cin u v w;dp[u][v][0] w;dp[v][u][0] w;}for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {dp[i][j][k] min(dp[i][j][k - 1], dp[i][k][k - 1] dp[k][j][k - 1]);}}}cin q;while (q--) {cin start ed;cout (dp[start][ed][n] 10009 ? -1 : dp[start][ed][n])endl;}
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}注意事项
dp数组不应该设置为最大值INT_MAX否则会相加溢出导致数据异常 vector vectorvectorintdp(n 1, vectorvectorint(n 1, vectorint(n 1, 10009)));
空间优化版
直接删去了k这一个维度因为利用更新后的数据(第k层的)dp[i][k] dp[k][j]更新自己同一层(第k层的)数据也能得到正确结果
#includebits/stdc.h
using namespace std;
using ll long long;
int n, m, u, v, w,q,start,ed;
void solve() {cin n m;vector vectorintdp(n 1,vectorint(n1,10009));//dp数组while (m--) {cin u v w;dp[u][v] w;dp[v][u] w;}for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {dp[i][j] min(dp[i][j], dp[i][k] dp[k][j]);}}}cin q;while (q--) {cin start ed;cout (dp[start][ed] 10009 ? -1 : dp[start][ed])endl;}
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}多次使用dijsktra算法
核心思路
将dijsktra定义为函数传入dist数组的拷贝(没有引用)作参数,传入st,ed分别作为源点和终点在函数内初始化dist数组
个人代码
#includebits/stdc.h
using namespace std;
using ll long long;
int n, m, s, e, v,q,st,ed;//su,ev,vw;
void dijkstra(vectorvectorintgrid, vectorboolvisited, vectorintdist,int st,int ed) {
//vectorboolvisited和vectorintdist一定不能传入引用的形式dist[st]0;//一定要在这里初始化dist[st]for (int i 1; i n - 1; i) {int temp INT_MAX;int cur 0;for (int j 1; j n; j) {if (!visited[j] dist[j] temp) {temp dist[j];cur j;}}visited[cur] true;for (int j 1; j n; j) {if (grid[cur][j] ! INT_MAX !visited[j] dist[cur] grid[cur][j] dist[j]) {dist[j] dist[cur] grid[cur][j];}}}cout (dist[ed] INT_MAX ? -1 : dist[ed]) endl;
}
void solve() {cin n m;vectorvectorintgrid(n 1, vectorint(n 1, INT_MAX));vectorboolvisited(n 1, false);vectorintdist(n 1, INT_MAX);while (m--) {cin s e v;grid[s][e] v;grid[e][s] v;}cin q;while (q--) {cin st ed;dijkstra(grid, visited, dist,st,ed);}}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}本文参考于代码随想录
