等保二级网站建设方案,系统管理平台,WordPress文章生成海报代码,网站建设毕业设计总体规划参考#xff1a;约会怎么走到目的地最近呢#xff1f;一文讲清所有最短路算法问题-CSDN博客
有4个城市8条路#xff0c;公路上的数字表示这条公路的长短#xff0c;并且路是单向的#xff0c;现在要求我们求出任意两个城市之间的最短路程#xff0c;也就是求任意两个点之…参考约会怎么走到目的地最近呢一文讲清所有最短路算法问题-CSDN博客
有4个城市8条路公路上的数字表示这条公路的长短并且路是单向的现在要求我们求出任意两个城市之间的最短路程也就是求任意两个点之间的最短路经这就是多源最短路问题。 1.假设我们只允许经过1号城市求任意两城市之间的最短路程应该如何求呢
只需判断e[ i ][1]e[1][ j ]是否比e[ i ][ j ]要小即可。
for(int i1;in;i) //遍历起点城市for(int j1;jn;j) //遍历被缩小距离的城市if(e[i][j] e[i][1]e[1][j]) //如果我通过1城市进行中转后的距离比你现在直接到要近e[i][j]e[i][1]e[1][j];//则直接赋值给给e[i][j]即可2.假设我们允许经过1号城市和2号城市求任意两点之间的最短路程应该如何求呢
我们需要在只允许经过 1号顶点时任意两点的最短路程的结果下再判断如果经过2号顶点是否可以使得 i 号顶点到 j 号顶点之间的路程变得更短即判断e[ i ][2]e[2][ j ] 是否要比 e[ i ][ j ] 要小。
//经过一号顶点
for(int i1;in;i)//遍历起点城市for(int j1;jn;j)//遍历被缩小距离的城市if(e[i][j] e[i][1]e[1][j])//如果我通过1城市进行中转后的距离比你现在直接到要近e[i][j]e[i][1]e[1][j];//则直接赋值给给e[i][j]即可//经过二号顶点
for(int i1;in;i)//遍历起点城市for(int j1;jn;j)//遍历被缩小距离的城市if(e[i][j] e[i][2]e[2][j])//如果我通过2城市进行中转后的距离比你现在直接到要近e[i][j]e[i][2]e[2][j];//则直接赋值给给e[i][j]即可以此类推如果我们允许经过从1号到n号所有城市求两点间最短路程可以写出代码
for(int k1;kn;k) //一共有n个城市{for(int i1;in;i) //遍历起点城市{for(int j1;jn;j) //遍历需要缩短距离的城市{d[i][j]min(d[i][j],d[i][k]d[k][j]); //经过k号城市进行中转的距离与原来直接从起点到终点的距离是否有缩小}}}
这也就是Floyd算法了Floyd属于多源最短路径算法能够求出任意2个顶点之间的最短路径支持负权边。
题目描述
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环边权可能为负数。
再给定 k 个询问每个询问包含两个整数 x 和 y表示查询从点 x 到点 y 的最短距离如果路径不存在则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
接下来 k 行每行包含两个整数 x,y表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行每行输出一个整数表示询问的结果若询问两点间不存在路径则输出 impossible。
数据范围
1≤n≤200, 1≤k≤n^2 1≤m≤20000, 图中涉及边长绝对值均不超过 1000010000。
输入样例
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3输出样例
impossible
1
思路就像上面一样遍历所有点求从起点经过中间的点中转后到终点的最短距离 for(int k1;kn;k) //一共有n个城市{for(int i1;in;i) //遍历起点城市{for(int j1;jn;j) //遍历需要缩短距离的城市{d[i][j]min(d[i][j],d[i][k]d[k][j]); //经过k号城市进行中转的距离与原来直接从起点到终点的距离是否有缩小}}}
示例代码
// 这道题是多源点问题有多个x到y的路径要求
#includecstring
#includeiostream
#includealgorithm
using namespace std;const int N210,INF1e9; //表示正无穷
int n,m,q;
int d[N][N]; //d[i][j]表示从i到j的最短路长度void floyd()
{for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){d[i][j]min(d[i][j],d[i][k]d[k][j]);}}}
}int main()
{scanf(%d%d%d,n,m,q);for(int i1;in;i){for(int j1;jn;j){if(ij) d[i][j]0; //自环边的权值设成了0是为了干掉自环因为不存在负权回路自环没有意义else d[i][j]INF;}}while(m--){int a,b,c;scanf(%d%d%d,a,b,c);d[a][b]min(d[a][b],c); //输入每条边只保留最短边}floyd();while(q--){int a,b;scanf(%d%d,a,b);int td[a][b];if(tINF/2) puts(impossible); //不能走到终点但由于负数边权的存在终点的距离可能被其他长度是正无穷的距离更新else printf(%d\n,t);}return 0;
}
