用途
用来确定一个点到其他几个点的最近距离（不含负权的有向图）
算法思想
1.以各点到初始点的距离为最近距离（即直接与初始点相连的边的权），如果不直接相连的距离则为无穷。 2.选取这些边最短的，并判断该边的head与其他的点是否相连，如果相连之后的距离小于目前的最小距离，就更新初始点到各点的最小距离。（此时选出的最短的这条边的权就是他的head到初始点的最近距离，这时已经不需要判定该head距离初始点的最近距离，为其做上标记） 3.不断重复2操作知道所有的点都被标记，这是就选出了最近距离。
代码实现
代码语言：javascript复制 int a,b; //a代表的是节点数，b代表的是弧的数量
int start； //start代表的是初始位置
int path[a][a]; //邻接矩阵
int path2[a], p2[a]; //path2待选择的路径，已选择好的最短路径
for(int i=0;i<a;i )
{
for(int j=0;j<a;j )
{
path[i][j]=10000; //对对邻接矩阵进行初始化
}
}
for(int i=0;i<a;i )
{
p2[i]=10000; //对最短路径进行初始化
}
string p[a];
int a2,b2,length;
for(int i=0;i<b;i )
{
cin>>a2>>b2>>length;
path[a2][b2]=length;
} //输入邻接矩阵的内容
for(int i=0;i<a;i )
{
path2[i]=path[start][i];
}
for(int i=0;i<a-1;i )
{
int h=pd(path2,a); //pd是自定义的一个找最小权边的函数
if(h!=-1) // h=-1说名path2中的未标记节点到初始点最近距离的值还是10000，即包括初始点在内的已标记节点与他们都无边相连，初始点无法到达他们，则循环无需进行下去
{p2[h]=path2[h];
path2[h]=0;
for(int j=0;j<a;j )
{
if((p2[h] path[h][j])<path2[j])
{
path2[j]=p2[h] path[h][j];
p[j]=p[h];
p[j].push_back(48 h);
}
}
}
else{
break;
}
}
