如何建设购物网站,天津地区网站建设,江苏常州建设银行网站,世界500强企业logo图片目录
一、概念
二、思路
三、代码 一、概念
在前面的学习中#xff0c;我们已经接触了Dijkstra、Bellman-Ford等单源最短路径算法。但首先我们要知道何为单源最短路径#xff0c;何为多源最短路径
单源最短路径#xff1a;从图中选取一点#xff0c;求这个点到图中其他…目录
一、概念
二、思路
三、代码 一、概念
在前面的学习中我们已经接触了Dijkstra、Bellman-Ford等单源最短路径算法。但首先我们要知道何为单源最短路径何为多源最短路径
单源最短路径从图中选取一点求这个点到图中其他节点的最短路径多源最短路径从图中任选两个节点我们都能知道这两点间的最短路径
Floyd多源最短路径算法可用于求图中任意两点间的最短路径长其核心思路在于依次将每个节点作为路径的中间点来更新其他任意两点的较优解最后得到全局最优解 二、思路
1.首先我们需要一个图和二维数组g、path 其中
g用于存储从i到j的最短路径长度path用于存储从i到j的最短路径的终点 的 前继节点 例如初始时从1到2的最短路径就是权重为6的边其终点为2而对于这条路径而言2的前继节点为1因此path[1][2] 1 g(0)和path(0)意为矩阵g和path的初始态。因为初始时两个节点之间的最短路径就是他们之间的边因此我们在初始化这两个数组时只需要按照样例输入的边填写矩阵g即可
若从i到j之间没有边则填最大值即可例如g[3][2] MAX因为没有从3指向2的边
而矩阵path在初始化时按照上面的规则初始化即可例如初始从3到1的最短路径就是3-1终点为1前继节点为3因此path[3][1] 3
2. 从1号节点开始将每个节点作为任意两个节点的最短路径的中间点
有的人听到这里可能已经懵了我们跟着图慢慢走 此时g(0)、path(0)变为g(1)和path(1)代表接下来要更新 i-1-j 的最短路径
但是我们并不需要将矩阵g和矩阵path中的所有值都更新例如g[1][2]判断1-1-2的路径是否比1-2的最短路径更短是不具有价值的。两个矩阵中如果行标和中间节点一样、列标和中间节点一样或者行标和列标一样的话我们直接跳过即可
因此只有2-1-3的情况和3-1-2的情况需要讨论 带虚线的位置代表不需要判断
可以看到2-1-3的距离为2-1的最短距离加1-3的最短距离即g[2][1]g[1][3] 23这个距离并不比g[2][3]小因此不需要更新
而3-1-2的距离为11小于原来的值MAX因此更新同时path[3][2]也更新为3-1-2的终点的前继节点即1
3.重复第二步直到所有节点都已作为中间点 1-2-3的距离为g[1][2]g[2][3] 10比原来的13更小因此将g[1][3]更新path[1][3] 2
3-2-1的距离为g[3][2]g[2][1] 21比g[3][1]大不更新 1-3-2的距离为21比g[1][2]大不更新
2-3-1的距离为g[2][3]g[3][1] 9比原来的10更小因此将g[2][1]更新path[2][1] 3
至此我们就得到了图中任意两点间的最短路径长度了
而最短路径本身则可以根据矩阵path中的值推出来例如要求从2到1的最短路径首先知道终点为节点1根据path[2][1]知道下一个节点3再根据path[2][3]知道下一个节点2最后path[2][2]为-1说明路径走到结尾因此完整的最短路径就为2-3-1 三、代码 #include bits/stdc.h
#define int long long
#define endl \n
#define debug(x) cout #x x \n
#define INF 0x3f3f3f3f
using namespace std;#define N 210
#define M 20010int n, m, k;
int g[N][N]; //存储从i到j的最短路径长度
int path[N][N] {-1}; //path[i][j]存储从i到j最短路径的终点 的 前继节点void Floyd()
{for(int i 1; i n; i){g[i][i] 0; //自己到自己的路径长度设置为0path[i][i] -1; //自己到自己的路径设置为-1}for(int k 1; k n; k) //代表从i经过k到j的最短路径{for (int i 1; i n; i) //第i行{for (int j 1; j n; j) //第j列{if(i j || i k || j k) //多余情况continue;if(g[i][k] g[k][j] g[i][j]) //从i经过k到j的最短路径 比 原先从i到j的最短路径更短{g[i][j] g[i][k] g[k][j]; //更新从i到j的最短路径path[i][j] path[k][j]; //更新从i到j最短路径的终点 的 前继节点}}}}
}void solve()
{memset(g, 0x3f, sizeof g);cin n m k;for(int i 0;i m; i){int a, b, w;cin a b w;g[a][b] min(g[a][b], w); //可能存在重边path[a][b] a; //初始时从a到b最短路径终点的前继节点就是a本身}Floyd(); //Floyd算法for (int i 0; i k; i){int a, b;cin a b;if(g[a][b] INF / 2)cout impossible endl;elsecout g[a][b] endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t 1;//cin t;while(t--)solve();return 0;
}
完.
