欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【图论】【最短路】最短路径问题

程序员文章站 2023-12-27 13:55:57
...

Description

平面上有n个点(N<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点直线的距离。现在的任务是找出从一点到另一点之间的最短路径。

Input

输入文件short.in,共有n+m+3行,其中:
第一行为一个整数n。
第2行到第n+1行(共n行),每行的两个整数x和y,描述一个点的坐标(以一个空格隔开)。
第n+2行为一个整数m,表示图中的连线个数。
此后的m行,每行描述一条连线,由两个整数I,j组成,表示第i个点和第j个点之间有连线。
最后一行:两个整数s和t,分别表示源点和目标点。

Output

输出文件short.out仅一行,一个实数(保留两位小数),表示从S到T的最短路径的长度。

Sample Input

5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5

Sample Output

3.41


解题思路

最短路模板,输入的时候需要用公式 求出两个连接的点的距离(边权)

Ford算法
未更新的为蓝点,更新过的为白点
dis[1dis[1~5]=5]=∞
【图论】【最短路】最短路径问题

11出发,11标记为白点
dis[1]=0dis[2dis[1]=0,dis[2~5]=5]=∞
【图论】【最短路】最短路径问题
枚举所有的边
11更新了2342、3、4
dis[1]=0dis[2]=2dis[3]=1dis[4]=3dis[5]=dis[1]=0,dis[2]=2,dis[3]=1,dis[4]=3,dis[5]=∞

【图论】【最短路】最短路径问题
再次枚举所有边,白点并不限制更新对象,既可以更新蓝点也可以更新白点
33更新了44
22更新了55
dis[1]=0dis[2]=2dis[3]=1dis[4]=2dis[5]=4dis[1]=0,dis[2]=2,dis[3]=1,dis[4]=2,dis[5]=4

至此,最短路就求完了(✿✿ヽ(°▽°)ノ✿)


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,S,T,x[2000],y[2000],lx[2000],ly[2000];
double s[2000],dis[2000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&lx[i],&ly[i]);
		s[i]=sqrt(pow(double(x[lx[i]]-x[ly[i]]),2)+pow(double(y[lx[i]]-y[ly[i]]),2));//求边权
	}
	scanf("%d%d",&S,&T);
	memset(dis,0x7f,sizeof(dis));
	dis[S]=0;//起点设为0
	for(int i=1;i<n;i++){//
		bool t=0;
		for(int j=1;j<=m;j++){
			if(dis[lx[j]]+s[j]<dis[ly[j]]){//
				dis[ly[j]]=dis[lx[j]]+s[j];//
				t=1;                       //
			}                              //判断这条边可不可以松弛连接的两点
			if(dis[ly[j]]+s[j]<dis[lx[j]]){//
				dis[lx[j]]=dis[ly[j]]+s[j];//
				t=1;
			} 
		}
		if(!t)break;//如果没有边可以松弛,就可以直接退出
	}
	printf("%.2lf",dis[T]);
}
相关标签: 图论 最短路

上一篇:

下一篇: