C语⾔实现最短路径⼀：实验⽬的
(1)最短路径求解实验帮助学⽣熟练掌握图的顶点、边的概念及其存储实现。
(2)掌握图的基本运算，以及利⽤图解决实际问题的基本⽅法。
⼆：实验内容
（1）图的存储表⽰：输⼊图的顶点和图的边。并转换为图的存储结构表⽰。
（2）求解从⼀个城市出发到另⼀个城市的最短路径
三：实验要求
（1）根据实验内容编写程序，上机调试并获得运⾏结果。
（2）撰写实验报告。
四：程序清单、调试和测试结果及分析
//最短路径
/
/有向图的⽹络存储结构，
//校园导航
//(1)计算出给定起点到终点之间的最短距离
//(2)输出该路线
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<limits>
#include<stack>
using namespace std;
const int ERROR=-1;
const int MAXVEX=30;
const int MAXNAME=20;
const int MAX_INT=numeric_limits<int>::max();
typedef char VexType[MAXNAME];
cstring转为int
typedef int AdjType;
typedef struct{
int n;          //顶点个数
VexType vexs[MAXVEX];      //顶点信息
AdjType arcs[MAXVEX][MAXVEX];  //边信息
}GraphMatrix;
typedef struct{
int len;            //最短路径长度
int pre;            //前⼀顶点
}ShortPath;
int Locate(GraphMatrix *g,VexType u)  //寻u在⽹络中的序号
{
for(int i=0;i<g->n;++i)
{
if(strcmp(u,g->vexs[i])==0)    //如果
return i;
}
return ERROR;
}
//学校建筑物的信息存进去
void Init_route(GraphMatrix *h)
{
VexType va,vb;  //⽤于保存节点的临时变量
int weight;  //⽤于保存权重的临时变量
GraphMatrix *p=h;
int n;
printf("请输⼊顶点的个数：");
scanf("%d",&n);
p->n=n;
p->n=n;
getchar();      //吸收掉回车键
for(int i=0;i<n;i++)
{
printf("请输⼊第%d顶点的名称:",i+1);
scanf("%s",p->vexs[i]);
printf("\n");
}
for(int i=0;i<n;i++)    //将所有的联系路径设为⽆穷
for(int j=0;j<n;j++)
{
if(i==j)
p->arcs[i][j]=0;
else
p->arcs[i][j]=MAX_INT;
}
int m;      //请输⼊边的条数；
printf("请输⼊边的条数：");
scanf("%d",&m);
for(int k=0;k<m;k++)
{
scanf("%s%s%d",va,vb,&weight);
int i,j;
i=Locate(p,va);
j=Locate(p,vb);
if(i!=ERROR&&j!=ERROR)
p->arcs[i][j]=weight;
else
printf("输⼊错误，请您仔细检查\n");
}
printf("初始化完毕！\n");
}
//迪杰克拉斯算法
void Dijkstra(GraphMatrix *pgraph,ShortPath dist[],int start)
{
int i,j,min_;
AdjType minw;
dist[start].len=0;
dist[start].pre=0;
pgraph->arcs[start][start]=1;
for(int i=0;i<pgraph->n;++i)
{
dist[i].len=pgraph->arcs[start][i]; //初始距离到顶点距离赋值        if(dist[i].len!=MAX_INT)
dist[i].pre=start;
else
dist[i].pre=-1;
}
dist[start].pre=-1;
for(i=0;i<pgraph->n;i++)
{
minw=MAX_INT;
min_=start;
for(j=0;j<pgraph->n;j++)
if((pgraph->arcs[j][j]==0)&&(dist[j].len<minw))
{
minw=dist[j].len;
min_=j;
}
if(min_==0)
break;
pgraph->arcs[min_][min_]=1;
for(j=0;j<pgraph->n;j++)
{
if(pgraph->arcs[j][j]==1)
if(pgraph->arcs[j][j]==1)
continue;
if(dist[j].len>dist[min_].len+pgraph->arcs[min_][j]&&dist[min_].len+pgraph->arcs[min_][j]>0)
{
dist[j].len=dist[min_].len+pgraph->arcs[min_][j];
dist[j].pre=min_;
}
}
}
}
int main()
{
GraphMatrix graph;
ShortPath path[MAXVEX];
int tmp,cnt=0,pre=-1;
int temppath[MAXVEX];
int m,n;
VexType va,vb;
long totallen=0;
long curlen=0;
Init_route(&graph);
printf("\n请输⼊您要查询的起点和终点:\n");
scanf("%s%s",va,vb);
m=Locate(&graph,va);
n=Locate(&graph,vb);
if(m!=ERROR&&n!=ERROR)
{
Dijkstra(&graph,path,m);
for(tmp=0;tmp<MAXVEX;tmp++)
temppath[tmp]=-1;
pre=n;
while(path[pre].pre!=-1)
{
temppath[cnt]=pre;
pre=path[pre].pre;
cnt++;
}
temppath[cnt]=m;
if(cnt<=0)
if(m!=n)
printf("%s<->%s⽆路可⾛!\n",graph.vexs[m],graph.vexs[n]);
else
printf("您输⼊的的顶点重合");
else{
tmp=cnt;
printf("%s->",graph.vexs[temppath[tmp]]);
for(;tmp>0;--tmp)
{
printf("%s(%d)->",graph.vexs[temppath[tmp-1]],graph.arcs[temppath[tmp]][temppath[tmp-1]]);                totallen+=graph.arcs[temppath[tmp]][temppath[tmp-1]];
}
printf("共：%d\n",totallen);
}
}
else
printf("%s->%s中不存在的建筑，请您仔细检查！!",va,vb);
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。