packagecom.cn.datastruct;importjava.util.Scanner;//最短路径求解
public classDistMin {static classGraphMatrix{static final int MaxNum=20;char[] Vertex=new char[MaxNum];  //保存顶点信息(序号或字母)
int GType;    //图的类型(0：无向图，1：有向图)
int VertexNum;        //顶点的数量
int EdgeNum;        //边的数量
int[][] EdgeWeight=new int[MaxNum][MaxNum];        //保存边的权
int[] isTrav=new int[MaxNum];        //遍历标志
}static final int MaxValue=65535;    //最大值(可设为一个最大整数)
static int[] path=new int[GraphMatrix.MaxNum];    //两点经过的顶点集合的数组
static int[] tmpvertex=new int[GraphMatrix.MaxNum];  //最短路径的起始点集合
static Scanner input=newScanner(System.in);//创建邻接矩阵图
static voidCreateGraph(GraphMatrix GM){inti,j,k;int weight;     //权
char EstartV,EendV;        //边的起始顶点
System.out.printf("输入图中各顶点信息\n");for(i=0;i
System.out.printf("第%d个顶点：", i+1);
GM.Vertex[i]=(input.next().toCharArray())[0];  //保存到各顶点的数组元素中
}
System.out.printf("输入构成各边的顶点及权值：\n");for(k=0;k
System.out.printf("第%d条边：", k+1);
EstartV=input.next().charAt(0);
EendV=input.next().charAt(0);
weight=input.nextInt();for(i=0;EstartV!=GM.Vertex[i];i++);      //在已有顶点中查找始点
for(j=0;EendV!=GM.Vertex[j];j++);        //在已有的顶点中查找终点
GM.EdgeWeight[i][j]=weight;          //对应位置保存权值，表示有一条边
if(GM.GType==0){        //若是无向图
GM.EdgeWeight[j][i]=weight;        //在对角位置保存权值
}
}
}//清空矩阵
static voidClearGraph(GraphMatrix GM) {inti, j;for (i = 0; i < GM.VertexNum; i++) {for (j = 0; j < GM.VertexNum; j++) {
GM.EdgeWeight[i][j]= MaxValue; //设置矩阵中各元素的值为MaxValue
}
}
}//输出邻接矩阵
static voidOutGraph(GraphMatrix GM) {inti, j;for (j = 0; j < GM.VertexNum; j++) {
System.out.printf("\t%c", GM.Vertex[j]); //在第一行输出顶点信息
}
System.out.println();for (i = 0; i < GM.VertexNum; i++) {
System.out.printf("%c", GM.Vertex[i]);for (j = 0; j < GM.VertexNum; j++) {if (GM.EdgeWeight[i][j] == MaxValue) { //若权值为最大值
System.out.printf("\tZ"); //以Z表示无穷大
} else{
System.out.printf("\t%d", GM.EdgeWeight[i][j]); //输出边的权值
}
}
System.out.println();
}
}//最短路径算法
static void distMin(GraphMatrix GM,int vend){    //vend为结束点
int[] weight=new int[GraphMatrix.MaxNum];        //某终止点到各顶点的最短路径长度
inti,j,k,min;
vend--;for(i=0;i
weight[i]=GM.EdgeWeight[vend][i];
}for(i=0;i
if(weight[i]0){    //有效权值
path[i]=vend;
}
}for(i=0;i
tmpvertex[i]=0;            //初始化顶点集合为空
}
tmpvertex[vend]=1;        //选入顶点vend
weight[vend]=0;for(i=0;i
min=MaxValue;
k=vend;for(j=0;j
min=weight[j];
k=j;
}
}
tmpvertex[k]=1;            //将顶点k选入
for(j=0;j
if(tmpvertex[j]==0&&weight[k]+GM.EdgeWeight[k][j]
weight[j]=weight[k]+GM.EdgeWeight[k][j];
path[j]=k;
}
}
}
}public static voidmain(String[] args) {
GraphMatrix GM=new GraphMatrix();   //定义保存邻接表结构的图
String go;intvend;inti,k;
System.out.println("求解最短路径问题！");do{
System.out.print("请先输入生成图的类型：");
GM.GType=input.nextInt();   //图的种类
System.out.print("请输入图的顶点数量：");
GM.VertexNum=input.nextInt();         //输入图中顶点数
System.out.print("请输入图的边的数量：");
GM.EdgeNum=input.nextInt();        //输入图中边数
ClearGraph(GM);            //清空图
CreateGraph(GM);        //生成邻接表结构的图
System.out.print("\n请输入结束点：");
vend=input.nextInt();
distMin(GM,vend);
vend--;
System.out.printf("\n个顶点到达顶点%c的最短路径分别为(起始点-结束点)：\n",GM.Vertex[vend]);for(i=0;i
if(tmpvertex[i]==1){
k=i;while(k!=vend){
System.out.printf("顶点%c-", GM.Vertex[k]);
k=path[k];
}
System.out.printf("顶点%c\n", GM.Vertex[k]);
}else{
System.out.printf("%c-%c:无路径\n", GM.Vertex[i],GM.Vertex[vend]);
}
}
System.out.println("\n继续玩吗(y/n)?");
go=input.next();
}while(go.equalsIgnoreCase("y"));
System.out.println("游戏结束！");
}
}

为何地图上的航线是曲线
如果我们观察地图上的航线，就会发现航线是弯曲的。
基本上可以认为地球是个球体，如果飞机在两个城市之间飞行，最好的飞行线路是取这两个城市之间的最短距离。这其实课看成球面上任意两点之间的最短距离。过球面上的任意两点以及球心可以做一个截平面，与球面的截痕为一个圆，这个圆的大小不随两点不同而变化，半径都是球半径。这个圆是任意平面与球面相截得到的所有不同的圆中，半径最大的，因此叫做大圆。而只要你沿着球表面做线连接任意两个点，曲线长度最短的一定是这个大圆的劣弧长度。航线按两个城市之间的大圆弧航行才最经济。地图是球面向平面做投影做出来的，所以我们看到的航线就是曲线了。
定理：球面上任意两点间的距离以大圆最短
初等几何的观察
如图AB是连接A,B两点的大圆弧，C是AB弧上的任意一点，过C做以A,B为极点的圆,设AF,GF，GB为一条球面曲线，且BG是大圆弧，AF也是大圆弧
则CB=BG,AC=AF,但AF+FG+GB>AF+GB=AC+CB=AB.
如果B,E,D,A是另外一条球面上的曲线，过B,D,A的球面三角形中AD+BD>AB,
过E,B,A的球面三角形中亦有BE+AE>AB。
微积分证明
 下面我们利用球面坐标系与微积分给出一个精确的证明。
令A,B是半径为R的球面上的任意两点，C为球心，大圆弧长可以表达为
以C为中心建立直角坐标系，让A在z轴上，则球面上任意一点P的坐标可以写成：
空间中任意曲线的长度可以定义为：
其中s是参数，对球面曲线就有
所以
上式严格成立，也就是要求不论s取值如何都不能离开大圆弧AB时等式严格成立，这就证明了球面上两点的最短距离为大圆弧。这个距离被高斯称为球面测地线。

    两点之间最短距离  

 

 

 
 这是我的一个测试，也是我学习html的/起点，他们说一个合格的程序员必须学会html，我比他们起步晚了一些，可是我认为还来的及，以后我就用html来记录我的学习记录了。
 
 

 
 问题的提出：

 在二维平面的n个点上，找出其中的一对点，使得在n个点组成的所有的点中，该点对的距离最小。
 
 

 
 一维：最接近点对问题 
 
 方法一：（暴力法）

   直接使用双层遍历来计算每一对点的距离，另外新建一个变量记录两点之间距离最小的值，但是如此一来时间复杂度就变为O(n2),
 
 
方法二：(分治法）

 分治法的思路:
 

 

 
划分成子规模点集S1和S2；
 
找到S1和S2的最小距离d；
 
合并S1和S2：利用d在S1的(m-d,m]和S2(m,m+d]中找到最大点和最小点，即p3和q3.选出最小距离，完成合并。
 
 

 ![示意图](https://img-blog.csdnimg.cn/20201004201704741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTExOTY0,size_16,color_FFFFFF,t_70#pic_center)
m如何选择

m=(max(s)+min(s))/2;


代码：
talking is cheap,show me the code;
/*根据算法随便写的，返回的是两个点之间最小的距离，不是两个点的坐标，如果有问题，欢迎指正*/
/*这里的坐标默认为正序的*/
#include<iostream>
#include<vector>
using namespace std;
int search(vector<int> target)
{   
int n=target.size();   
if(n<2)   //如果分到一个元素就返回最大数值
return INT_MAX;   
int mid=n/2;   //中线
vector<int> temp_left;  
 vector<int> temp_right;   temp_left.insert(temp_left.begin(),target.begin(),target.begin()+mid); //中线分割  temp_right.insert(temp_right.begin(),target.begin()+mid,target.end());  
 int p=search(temp_left);  
 int q=search(temp_right);  
 int d=temp_right.front()-temp_left.back();  
 cout<<temp_right.front()<<" "<<temp_left.back()<<endl;  
return d>min(p,q)?min(p,q):d;}//返回两边和贯穿中间的最小的两点距离
 int main(){    
 int a[6]={-9,-6,0,4,7,9};    
 vector<int> target(a,a+6);    
cout<<search(target);    
return 0;
}

 二维最接近点的问题：

思路与一维的最接近点对相似。


选取中垂线l：x=m来作为分割直线。
递归的在S1和S2找出其最小距离d1和d2，并设d=min{d1,d2}，S中最接近点对或是d，或者是某个{p，q}
合并起来


// 随便写思路的如果有误，请指正（注意返回的是两点之间的距离，不是坐标）
#include <iostream>
#include <math.h>
#include<algorithm>
using namespace std;
struct point
{
	int x, y;
};
double distance(struct point p1, struct point p2)
{
	return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y,2));
}
double search(struct point p[],int pl,int pr)
{
	if (pl == pr)
		return INT_MAX;
	int mid = (pl + pr) / 2;
	double d_left = search(p, pl, mid);
	double d_right = search(p, mid + 1, pr);
	double temp_d = min(d_left, d_right);
	while (abs(p[pl].y - p[mid].y) > temp_d&&pl < pr)//如果仅仅是单边距离就已经大于上一次比较返回的d就没必要在接下来的敌方继续比较了。
		pl++;
	while (abs(p[pr].y - p[mid].y) > temp_d&&pl < pr)
		pr--;
	for (int i = pl; i < pr; i++)
	{
		for (int j = i + 1; j < pr; j++)
		{
			if (temp_d < abs(p[i].x - p[j].x))//同理与上面的注释
				break;
			else
				temp_d = min(temp_d, distance(p[i], p[j]));//找到最小的距离
		}
	}
	return temp_d;
}
int main()
{
	struct point p[100];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> p[i].x;
		cin >> p[i].y;
	}
	cout<<search(p, 0, n - 1);
}

我有两个数据框。一个包含properties locations，另一个包含railway stations locations。
属性数据框样本(原始数据框由约700行组成)：
properties=pd.DataFrame({'propertyID':['13425','32535','43255','52521'],
'lat':[-37.79230,-37.86400,-37.85450,-37.71870],
'lon':[145.10290,145.09720,145.02190,144.94330]})
火车站数据框样本(原始数据框由约90行组成)：
stations=pd.DataFrame({'stationID':['11','33','21','34','22'],
'lat':[-37.416861,-37.703293,-37.729261,-37.777764,-37.579206],
'lon':[145.005372,144.572524,144.650631,144.772304,144.728165]})
我有一个函数来计算两个位置之间的距离
from math import radians, cos, sin, asin, sqrt
def haversine(lon1, lat1, lon2, lat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
r = 6378 # Radius of earth in kilometers
return c * r
我想找到每个属性与所有站点之间的距离。然后选择距离最短的车站。
我试图构造一个for循环，但它没有返回最短距离(分钟)
lst=[]
for stopLat in stations['lat']:
for stopLon in stations['lon']:
for propLat in properties['lat']:
for propLon in properties['lon']:
lst.append(haversine(propLon,propLat,stopLon,stopLat))
我的最终输出将如下所示。(每个属性都链接到最近的车站)。
stationID propertyID
11        52521
33        13425
21        32535
34        43255
关于如何解决此问题的任何建议都将有所帮助。谢谢
解决方案
这是一种解决方法，但我首先将两个数据框与一个附加的“键”合并。然后我使用apply计算距离：
properties['key'] = 1
stations['key'] = 1
df = properties.merge(stations,on='key')
del df['key']
df['distance'] = df.apply(lambda x: haversine(x['lon_x'],x['lat_x'],x['lon_y'],x['lat_y']),axis=1)
print(df)
df = df.loc[df.groupby("propertyID")["distance"].idxmin()]
df = df[['stationID','propertyID']]
print(df)
第一次打印：
propertyID    lat_x     lon_x stationID      lat_y       lon_y   distance
0       13425 -37.7923  145.1029        11 -37.416861  145.005372  42.668639
1       13425 -37.7923  145.1029        33 -37.703293  144.572524  47.723406
2       13425 -37.7923  145.1029        21 -37.729261  144.650631  40.415507
3       13425 -37.7923  145.1029        34 -37.777764  144.772304  29.129338
4       13425 -37.7923  145.1029        22 -37.579206  144.728165  40.650436
5       32535 -37.8640  145.0972        11 -37.416861  145.005372  50.428078
6       32535 -37.8640  145.0972        33 -37.703293  144.572524  49.504807
7       32535 -37.8640  145.0972        21 -37.729261  144.650631  42.047056
8       32535 -37.8640  145.0972        34 -37.777764  144.772304  30.138684
9       32535 -37.8640  145.0972        22 -37.579206  144.728165  45.397047
10      43255 -37.8545  145.0219        11 -37.416861  145.005372  48.738487
11      43255 -37.8545  145.0219        33 -37.703293  144.572524  42.971083
12      43255 -37.8545  145.0219        21 -37.729261  144.650631  35.510616
13      43255 -37.8545  145.0219        34 -37.777764  144.772304  23.552690
14      43255 -37.8545  145.0219        22 -37.579206  144.728165  40.101407
15      52521 -37.7187  144.9433        11 -37.416861  145.005372  34.043280
16      52521 -37.7187  144.9433        33 -37.703293  144.572524  32.696875
17      52521 -37.7187  144.9433        21 -37.729261  144.650631  25.795774
18      52521 -37.7187  144.9433        34 -37.777764  144.772304  16.424364
19      52521 -37.7187  144.9433        22 -37.579206  144.728165  24.508280
第二次印刷：
stationID propertyID
3         34      13425
8         34      32535
13        34      43255
18        34      52521
但是根据该输出站34总是最接近的。那是对的吗？
编辑：进一步的解释：
我曾经试图找到一种方法来将两个数据帧“合并”在一起，而这两个数据帧没有通常用于合并的通用唯一标识符。
我还想将一个数据帧的每一行与另一数据帧(在您的情况下，每个工作站具有每个属性)配对，以便能够比较那些条目。在我的研究中，我发现了使用虚拟密钥的巧妙解决方法。
在使用的这种解决方法中，我们看到每一行的键都是1，因此每一行将与其他数据帧中的每一行完全匹配我们想要的。
使用apply函数，您可以将任何函数逐行应用于数据框。