发广告平台有哪些免费,seo关键词排名优化工具,网站建设大作业,做外贸网站义乌在一些带权图里面#xff0c;时长需要我们求出某一点到另一点的最短距离#xff0c;floyed算法就是求最短路径的算法之一。其核心思想是经过某点中转#xff0c;加入A点到B点的距离是10#xff0c;B点到C点的距离为5#xff0c;A点到C点的距离为20#xff08;此图将距离设…在一些带权图里面时长需要我们求出某一点到另一点的最短距离floyed算法就是求最短路径的算法之一。其核心思想是经过某点中转加入A点到B点的距离是10B点到C点的距离为5A点到C点的距离为20此图将距离设定为权值而且该图为有向图。图的形状如下图所示
可以看出如果直接从A点到C点权值是20如果经过B点中转然后到达C点那么权值将变为15这就是A到C点的最短路径A-B-C。众所周知我们可以使用二维数组来存储图该二维数组被称为邻接矩阵当我们需要求最短路径时在中转时判断A点到C点的距离是否大于A点到B点再到C点的距离如果大于将更新邻接矩阵中的A到C点的距离为A点到B点再到C点的距离
if(length[A][C]length[A][B]length[B][C])length[A][C]length[A][B]length[B][C] 如果给了N个点那么将需要N次中转。因为邻接矩阵是一个NxN的二维数组我们需要遍历这个数组。如下一个例子首先给出点的个数和点的坐标在给出点的连接关系求出S点到T点的距离S和T为用户的输入数据
1.点的个数和坐标
4
1 1第一个点
2 3第二个点
3 4 第三个点
4 5第四个点
2.点的连接关系
1 2表示第一个点和第二个点是联通的
2 3
3 4
1 4
3.用户输入
S2,T4;
源码
floyed.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
void floyed(double arr[][10],int m) {//floyed算法for (int k 0; k m; k) {for (int i 0; i m; i) {for (int j 0; j m; j) {if ((i ! j ) (i ! k) (j ! k) (arr[i][k] arr[k][j] arr[i][j])) {arr[i][j] arr[i][k] arr[k][j];//更新邻接矩阵的值}}}}
}
main.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
#include cmath
#include vector
#include cstring
using namespace std;
void floyed(double arr[][10],int m) {//floyed算法for (int k 0; k m; k) {for (int i 0; i m; i) {for (int j 0; j m; j) {if ((i ! j ) (i ! k) (j ! k) (arr[i][k] arr[k][j] arr[i][j])) {arr[i][j] arr[i][k] arr[k][j];}}}}
}
int main(){vectorvectordouble array;int m;cin m;//点的个数for (int i 0; i m; i) {vectordouble nums;int x, y;cin x y;//横纵坐标nums.push_back(x);nums.push_back(y);array.push_back(nums);}int n;cin n;double arr[10][10];//邻接矩阵存图for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (i j) {arr[i][j] 0;}else {arr[i][j] 1000000007;//初始化邻接矩阵是最大值说明两点不可达}}}for (int i 0; i n; i) {int x, y;//两个点是否联通cin x y;x x - 1; //减一是因为邻接矩阵的下标从0开始y y - 1;arr[x][y] sqrt(pow(double(array[x][0]-array[y][0]),2)pow(double(array[x][1]-array[y][1]),2));//求出联通两点之间的距离arr[y][x] arr[x][y];}floyed(arr, m);//调用floyed算法int s, t;cin s t;s s - 1;t t - 1;cout arr[s][t] endl;return 0;
}
运行结果 第二个点到第四个点的最短距离为2.82843。该算法时间复杂度为O(N^3)虽然该算法可以处理带有负权值的图但是不能处理负环的图。负环又叫负权回路负权环指的是一个图中存在一个环里面包含的边的边权总和0。在存在负环的图中是求不出最短路径的因为只要在这个环上不停的兜圈子最短路径就会无限小。
