#include?
using?namespace?std;?
#define?INFINITY?100?
#define?MAXNODE?10?
typedef?char?ElemType;?
typedef?struct?
{?
int?adj;?
}ArcType;?
typedef?struct?
{?
char?*city[1];??
}name;?
typedef?struct?
{?
name?vertexs[MAXNODE];?
ArcType?arcs[MAXNODE][MAXNODE];?
int?vexnumarcnum;?
}GraphType;?
/*****************求該頂點的位置********************/?
int?LocateVex（GraphType?GElemType?*u[1]）?
{?
int?i=-1k;?
for（k=0;kif（**（G.vertexs[k].city）==**u）?
{?
i=k;?
break;?
}?
return?i;//失敗返回-1?
}?
/*************建立圖的鄰接矩陣******************/?
int?CreatDN（GraphType?*G）?
{?
int?ijkweight;?
ElemType?*u1[1]*u2[1];?
cout<<“請輸入圖的頂點數(shù)和弧數(shù)“;?
cin>>G->vexnum>>G->arcnum;?
for（i=0;ivexnum;i++）?
for（j=0;jvexnum;j++）?
G->arcs[i][j].adj=INFINITY;?
cout<<“請輸入頂點的信息“;?
for（i=0;ivexnum;i++）?
cin>>*G->vertexs[i].city;?
for（k=0;karcnum;k++）?
{?
cout<<“請輸入第“<cin>>*u1>>*u2>>weight;?
i=LocateVex（*Gu1）;?
j=LocateVex（*Gu2）;?
G->arcs[i][j].adj=weight;?
G->arcs[j][i].adj=weight;//無向圖?
}?
return?1;?
}?

/***********從一點到其余各點的最短距離***************/?
void?Dijkstra（GraphType?*Gchar?*u[1]char?*v[1]）?
{?
int?i1=LocateVex（*Gu）;?
int?i2=LocateVex（*Gv）;??
int?iktj;?
int?*d=new?int[5];??
int?*s=new?int[5];??
int?*p=new?int[5];??
int?way[20];//保存路徑用?
for（s[i1]=1i=0;ivexnum;i++）?//初始化數(shù)組dsp?
{??
if（i!=i1）?
{?
s[i]=0;d[i]=G->arcs[i1][i].adj;way[i]=i;?
if（d[i]p[i]=0;?
else?p[i]=-1;?
}?
}?
for（i=0;ivexnum;i++）??
{?
if（i!=i1）?
{?
t=INFINITY;k=1;??
for（j=0;jvexnum;j++）?
if（（j!=i1）&&（!s[j]）&&（d[j]{?
t=d[j];k=j;?
}?
s[k]=1;?
for?（j=0;jvexnum;j++）?
if（（j!=i1）&&（!s[j]）&&（d[j]>d[k]+G->arcs[k][j].adj））?
{?
d[j]=d[k]+G->arcs[k][j].adj;//d用于保存最短路徑的長度?
p[j]=k;?
way[j]=way[k]*10+j;//若該點屬于最短路徑，則保存該點?
}?
}?
}?

if（d[i2]==100）//不存在路徑?
cout<<“對不起，你不能去那“;?
else?
{?
cout<int?a[MAXNODE]b[MAXNODE]a1=0b1=0;?

cout<<“路徑為“<<*G->vertexs[i1].city;?
while（way[i2]/10!=0||way[i2]!=0）?
{?
a[a1]=way[i2]%10;?
a1++;way[i2]=way[i2]/10;?
}?
a1--;?
while（a1>=0）?
{?
b[b1]=a[a1];?
cout<<“->“<<*G->vertexs[b[b1]].city;?
b1++;a1--;?
}?
}?
cout<<“\n“<}?

/***************初始化圖**************************/?
GraphType?*chushihua（GraphType?*G）?
{?
G=（GraphType*）malloc（sizeof（GraphType））;?

G->vexnum=8;?
G->arcnum=9;?
for（int?i=0;ivexnum;i++）?
for（int?j=0;jvexnum;j++）?
G->arcs[i][j].adj=INFINITY;?
*G->vertexs[0].city=“前門“;
*G->vertexs[1].city=“圖書館“;
*G->vertexs[2].city=“教一樓“;?
*G->vertexs[3].city=“教二樓“;
*G->vertexs[4].city=“食堂“;
*G->vertexs[5].city=“水房“;?
*G->vertexs[6].city=“操場“;
*G->vertexs[7].city=“商店“;?
*G->vertexs[8].city=“公寓樓“;
*G->vertexs[9].city=“后門“;
G->arcs[0][1].adj=15;G->arcs[1][0].adj=15;?
G->arcs[0][2].adj=40;G->arcs[2][0].adj=40;?
G->arcs[0][3].adj=20;G->arcs[3][0].adj=20;?
G->arcs[2][3].adj=20;G->arcs[3][2].adj=20;?
G->arcs[2][4].adj

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????4512??2010-04-28?11:39??xioayuandaohang\123.cpp

?????文件?????731648??2011-06-20?09:37??xioayuandaohang\校園導航問題.doc

?????目錄??????????0??2011-06-20?09:42??xioayuandaohang

-----------?---------??----------?-----??----

???????????????736160????????????????????3