一个图一般都带有权值，而求一个点到另一个点的距离，则是比较基础的问题，下面为大家介绍四种遍历图的方法
一、弗洛伊德算法（暴力枚举法）
首先使用数组dis [ i ] [ j ]，i，j表示从 i 到 j 的距离，刚开始 i 和 j 没有联系时，初始化为无限（1<<30），输入后仍没联系时，通过中间点 k 来计算 dis[ i ] [ j ] = dis[ i ] [ k ] + dis[ k ] [ j ]，需要三重循环（讲例题时在再看代码实现）
二、迪杰斯克拉算法（抄水表法）
在知道起点和终点的情况下，设定数组dis [ i ]，表示从起点到 i 点的距离，从起点开始，一家一家的查找能与之相连的点（抄水表），再将已被查过的点做起点，继续抄水表（注意：抄过的家就不用抄了，所以要设一个bool数组），注意除起点外，其他dis都初始化为1<<30（讲例题时在再看代码实现）
下面来看一道例题：
最短路径问题
题目描述
平面上有n个点(n<=100)，每个点的坐标均在-10000～10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
输入
第1行：1个整数n
第2..n+1行：每行2个整数x和y，描述了一个点的坐标
第n+2行：1个整数m，表示图中连线的数量
接下来有m行，每行2个整数i和j，表示第i个点和第j个点之间有连线
最后1行：2个整数s和t，分别表示源点和目标点
输出
第1行：1个浮点数，表示从s到t的最短路径长度，保留2位小数
样例输入
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
样例输出
3.41
这道题两种方法都可以做，注意求两点A,B距离的方法AB=sqrt( pow( Xa - Xb ) + pow( Ya - Yb ) )，就是勾股定理
好，不说了，来看代码：
弗洛伊德算法：
<span style="font-size:14px;background-color: rgb(255, 255, 153);">#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double d[101][101];
int n,m,b,e;
void scan()//输入加初始化
{
int i,j,x,y;
double z[101][2];
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=1<<29;
for(i=1;i<=n;i++)
scanf("%lf%lf",&z[i][0],&z[i][1]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
d[x][y]=d[y][x]=sqrt(pow(z[x][0]-z[y][0],2)+pow(z[x][1]-z[y][1],2));//计算两点距离公式
}
scanf("%d%d",&b,&e);
d[b][b]=0;
}
void work()//弗洛伊德算法
{
int j,i,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[j][k]);//找最短路径
}
int main()
{
scan();
work();
printf("%.2lf",d[b][e]);//输出从b到e的距离
}</span>这就是传说中的暴力枚举
迪杰斯克拉算法：
<span style="font-size:14px;background-color: rgb(255, 255, 153);">#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double d[101],w[101][101];
bool v[101];
int n,m,b,e;
void scan()
{
int i,x,y;
double z[101][2];
memset(d,127,sizeof(d));
memset(w,127,sizeof(w));
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&z[i][0],&z[i][1]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
w[x][y]=w[y][x]=sqrt(pow(z[x][0]-z[y][0],2)+pow(z[x][1]-z[y][1],2));
}
scanf("%d%d",&b,&e);
d[b]=0;
}
void work()
{
int j,i;
for(i=1;i<=n;i++)
{
double minn=100000;
int minx;
for(j=1;j<=n;j++)
if(!v[j]&&minn>d[j])//抄水表式找点
{
minx=j;
minn=d[j];
}
v[minx]=1;
for(j=1;j<=n;j++)
d[j]=min(d[j],d[minx]+w[minx][j]);//判断最短路
}
}
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scan();
work();
printf("%.2lf",d[e]);//从起点到e
}</span>抄水表啊！！！
好了，今天只介绍这两种方法了，明天再来介绍后两种吧~(≧▽≦)/~