|
|
|
|
|
#include"type.h"
|
|
|
|
|
|
|
|
|
//Dijkstra算法
|
|
|
void Ppath(MatGrath &G,int path[],int w,int v) //前向递归查找路径上的顶点
|
|
|
{
|
|
|
int k;
|
|
|
k=path[w];
|
|
|
if (k==v) return; //找到了起点则返回
|
|
|
Ppath(G,path,k,v); //找顶点k的前一个顶点
|
|
|
printf("%s->",G.vexs[k].sight); //输出顶点k
|
|
|
}
|
|
|
|
|
|
|
|
|
void ShortestPath(MatGrath &G,int v,int w)//求两点之间的最短路径
|
|
|
{
|
|
|
int dist[MAXV],path[MAXV];
|
|
|
int s[MAXV];
|
|
|
int mindis,i,j,u;
|
|
|
for (i=0; i<G.vexnum; i++)
|
|
|
{
|
|
|
dist[i]=G.arc[v][i].length; //距离初始化
|
|
|
s[i]=0; //s[]置空
|
|
|
if (G.arc[v][i].length<INF) //路径初始化
|
|
|
path[i]=v; //v到i有边
|
|
|
else
|
|
|
path[i]=-1; //v到i没有边，置顶点i的前一个顶点为-1
|
|
|
}
|
|
|
s[v]=1;
|
|
|
path[v]=0; //源点编号v放入s中
|
|
|
for (i=0; i<G.vexnum; i++) //循环直到所有顶点的最短路径都求出
|
|
|
{
|
|
|
mindis=INF; //mindis置最小长度初值
|
|
|
for (j=0; j<G.vexnum; j++) //选取不在s中且具有最小距离的顶点u
|
|
|
if (s[j]==0 && dist[j]<mindis)
|
|
|
{
|
|
|
u=j;
|
|
|
mindis=dist[j];
|
|
|
}
|
|
|
s[u]=1; //顶点u加入s中
|
|
|
for (j=0; j<G.vexnum; j++) //修改不在s中的顶点的距离
|
|
|
if (s[j]==0)
|
|
|
if (G.arc[u][j].length<INF && dist[u]+G.arc[u][j].length<dist[j])
|
|
|
{
|
|
|
dist[j]=dist[u]+G.arc[u][j].length;
|
|
|
path[j]=u;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
if (s[w]==1)
|
|
|
{
|
|
|
printf(" 从%s到%s的最短路径长度为:%d米\t路径为:",G.vexs[v].sight,G.vexs[w].sight,dist[w]);
|
|
|
printf("%s->",G.vexs[v].sight); //输出路径上的起点
|
|
|
Ppath(G,path,w,v); //输出路径上的中间点
|
|
|
printf("%s\n",G.vexs[w].sight); //输出路径上的终点
|
|
|
}
|
|
|
if(s[w]==0)
|
|
|
printf("从%d到%d不存在路径\n",v,w);
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/***********************
|
|
|
功能：用Dijkstra算法求给出的一点到其余个点的最短路径
|
|
|
输入：源点
|
|
|
输出：地点的最短路程以及路径
|
|
|
***********************/ |
