# Shortest path problem [SSL 1613]

## subject

• Description

There are n points (n < = 100) in the plane, and the coordinates of each point are between - 10000 and 10000. There is a line between some of these points. If there is a line, it means that there is a path from one point to another, that is, there is a path between two points, and the distance of the path is the distance between two straight lines. The task now is to find the shortest path from one point to another.

• Input

The input file short.in has n+m+3 lines, where:
The first line is an integer n.
Line 2 to line n+1 of N, two integers x and y in each line, describing the coordinates of a point (separated by a space).
The n+2 is an integer m, indicating the number of lines in the graph.
In the following m lines, each line describes a line, which is composed of two integers i and j, indicating that there is a line between the I point and the J point.
The last line: two integers, s and t, represent the source point and the target point respectively.

• Output

The output file, short.out, has only one line, a real number (two decimal places reserved), representing the length of the shortest path from S to 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

## Solutions to problems

**>This is a shortest path problem.

Floyd algorithm (Floyd algorithm, also known as interpolation, is an algorithm for finding the shortest path between multiple source points in a given weighted graph)
Dijkstra algorithm (Dijkstra algorithm is to solve the shortest path problem (or single source point shortest path problem) from any vertex (source point) in the network to other vertices (end point). In fact, Dijkstra algorithm is the labeling method)
**

## Code (1) [Floyd]

```#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int a;
double f;
int n,i,j,k,x,y,m,s,e;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i],&a[i]);
scanf("%d",&m);
memset(f,0x7f,sizeof(f));
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
f[y][x]=f[x][y]=sqrt(pow(double(a[x]-a[y]),2)+pow(double(a[x]-a[y]),2));
}//Pretreatment
scanf("%d%d",&s,&e);
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j]))
f[i][j]=f[i][k]+f[k][j];
printf("%.2lf\n",f[s][e]); //Notice it's a decimal
return 0;
}

```

## Code (2) [Dijkstra]

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int a;
double c,f;
bool b;
int n,i,j,k,x,y,m,s,e;
double minl;
double maxx=1e30;
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
cin>>a[i]>>a[i];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
f[i][j]=maxx;
cin>>m;
for (i=1;i<=m;i++)
{
cin>>x>>y;
f[x][y]=f[y][x]=sqrt(pow(double(a[x]-a[y]),2)+pow(double(a[x]-a[y]),2));
}//Pretreatment
cin>>s>>e;
for (i=1;i<=n;i++)
c[i]=f[s][i];
memset(b,false,sizeof(b));
b[s]=true;
c[s]=0;
for (i=1;i<=n-1;i++)
{
minl=maxx;
k=0;
for (j=1;j<=n;j++)
if ((!b[j])&&(c[j]<minl))
{
minl=c[j]; //Record the minimum value each time
k=j; //Record the smallest node
}
if (k==0) break; //The current node has no surrounding nodes
b[k]=true; //Put new nodes into a set
for (j=1;j<=n;j++)
if (c[k]+f[k][j]<c[j]) c[j]=c[k]+f[k][j];//When a new point is added, update the distance between the current shortest path set and other points
}
printf("%.2lf\n",c[e]);
return 0;
}
```

Keywords: network

Added by nathus on Mon, 04 May 2020 15:15:57 +0300