最短路径问题

Algorithms
Dijkstra, 图论, 最短路

问题描述

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

输入

输入共 n+m+3 行，其中:
第一行为整数 n。
第 2 行到第 n+1 行 （共 n 行 ），每行两个整数 x 和 y，描述了一个点的坐标。
第 n+2 行为一个整数 m，表示图中连线 的个数。
此后的 m 行(m<=1000)，每行描述一条连线，由两个整数 i和 j 组成，表示第 i个点和第 j 个点之
间有连线 。
最后一行 ：两个整数 s 和 t，分别表示源点和目标点。

输出

输出仅一行，一个实数（保留两位小数），表示从 s 到 t 的最短路径长度 。

样例输入

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

样例输出

1
3.41

分析

顶点数较小，不加优化的 Dijkstra 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
const int INF=1<<29;
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x[110],y[110];
double dist[110][110];
// dist 数组即用作存边权的边集数组，若两点间有边则存其边权，没有则赋为 ∞
bool flag[110];// flag 用作标记每个端点是否已访问
double getdist(int x1,int x2,int y1,int y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
	memset(flag,0,sizeof(flag));
	int n,m,s,t;
	int i,j,k,pos;
	for(i=0;i<110;i++)
	{
		flag[i]=0;
		for(j=0;j<110;j++)
			dist[i][j]=INF;
	}
	cin >>n;
	for(i=1;i<=n;i++)
	{
		dist[i][i]=0;
		cin >>x[i]>>y[i];
	}
	cin >>m;
	for(i=1;i<=m;i++)
	{
		int a,b;
		cin >>a>>b;
		dist[a][b]=dist[b][a]=getdist(x[a],x[b],y[a],y[b]);
	}
	cin >>s>>t;
	flag[s]=1;
	for(i=1;i<=n;i++)
	{
		int minimum=INF;
		for(j=1;j<=n;j++)//找离 s 最近点 j
		{
			if(!flag[j] && dist[s][j]<minimum)
			{
				pos=j;
				minimum=dist[s][j];
			}
		}
		flag[pos]=1;
		for(j=1;j<=n;j++)
			if(!flag[j] && dist[s][pos]+dist[pos][j]<dist[s][j])
			//以找到的点为中间点，更新 s 到各顶点的最短距离
				dist[s][j]=dist[s][pos]+dist[pos][j];
	}
	printf("%.2lf\n",dist[s][t]);
	return 0;
}
分享到