2 u013247394 u013247394 于 2013.12.22 20:30 提问

我有一个数据结构最短路径程序,求解释里边程序每个步骤的意思

#include
#include
#define INFINITY 30000 //定义很大的数
#define MAX_VERTEX_NUM 20//最大的边数

using namespace std;

typedef struct{
string vexs[18];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
int vexnum,arcnum;//图的当前定点数和边数
}Graph;
void CreateUDN(Graph &G)//创建无向图
{
int i,j;
G.vexnum = 17;
G.arcnum = 21;
//初始化各个顶点的信息
G.vexs[1] ="入口";
G.vexs[2] ="人工湖";
G.vexs[3] ="后勤";
G.vexs[4] ="塑胶操场";
G.vexs[5] ="小广场";
G.vexs[6] ="12号楼";
G.vexs[7] ="13号楼";
G.vexs[8] ="学府公寓";
G.vexs[9] ="8号楼";
G.vexs[10] ="三教";
G.vexs[11] ="一教";
G.vexs[12] ="风雨操场";
G.vexs[13] ="第一餐厅";
G.vexs[14] ="排球场";
G.vexs[15] ="图书馆";
G.vexs[16] ="邮局";
G.vexs[17] ="二办";

//初始化存在边的权值
for(i=0;i<G.vexnum;++i)
   for(j=0;j<G.vexnum;++j)
      G.arcs[i][j]=INFINITY;
G.arcs[0][1]=G.arcs[1][0]=20;
G.arcs[0][4]=G.arcs[4][0]=20;
G.arcs[1][2]=G.arcs[2][1]=30;
G.arcs[2][3]=G.arcs[3][2]=20;
G.arcs[2][5]=G.arcs[5][2]=30;
G.arcs[4][5]=G.arcs[5][4]=10;
G.arcs[5][6]=G.arcs[6][5]=20;
G.arcs[5][7]=G.arcs[7][5]=50;
G.arcs[6][7]=G.arcs[7][6]=40;
G.arcs[6][8]=G.arcs[8][6]=10;
G.arcs[7][9]=G.arcs[9][7]=20;
G.arcs[7][10]=G.arcs[10][7]=20;
G.arcs[8][9]=G.arcs[9][8]=20;
G.arcs[8][13]=G.arcs[13][8]=30;
G.arcs[9][10]=G.arcs[10][9]=20;
G.arcs[10][11]=G.arcs[11][10]=20;
G.arcs[11][12]=G.arcs[12][11]=10;
G.arcs[12][15]=G.arcs[15][12]=20;
G.arcs[13][14]=G.arcs[14][13]=20;
G.arcs[14][15]=G.arcs[15][14]=20;
G.arcs[15][16]=G.arcs[16][15]=40;

}
//计算最短路径
void ShortestPath_FLOYD(Graph G,int D[17][17],int P[17][17])
{
int u,v,i,j,w;
for ( i=0; i<17; ++i)
for ( j=0; j<17; ++j)
{
D[i][j]=G.arcs[i][j];//初始化
P[i][j]= -1;//初始化
}

for( u=0; u for (v=0; v for ( w=0; w if (D[v][u]+D[u][w] {
D[v][w]=D[v][u]+D[u][w];
P[v][w]=u;//u为v到w最短路径上的前驱
}
}
//输出最短路径上经过的点
void ppath(Graph G,int path[17][17],int i,int j)
{
int k;
k=path[i][j];
if(k==-1)
return;
ppath(G,path,i,k);
cout cout";
ppath(G,path,k,j);
}

int main()
{
Graph G;
CreateUDN(G);
while(1)
{
cout<<"*****欢迎使用校园导航系统*****"< cout cout cout cout cout int choose;
cin>>choose;
if(choose == 1)
{
cout<<"17|"< cout cout cout cout cout cout cout cout cout cout }
if(choose == 2)
{
int num;
cout cin>>num;
cout<<G.vexs[num];
cout<<endl;
}
if(choose == 3)
{

    int v,w;
    int D[17][17];
    int P[17][17];
    ShortestPath_FLOYD(G, D, P);
    cout<<"请输入出发点和目的地的编号:";
    cin>>v>>w;
    cout<<"“";
    cout<<G.vexs[v];
    cout<<"”到“";
    cout<<G.vexs[w];
    cout<<"”的最短路线长为"<<D[v-1][w-1]<<endl;
    cout<<"为:";
    cout<<G.vexs[v];
    cout<<"->";
    ppath(G,P,v-1,w-1);
    cout<<G.vexs[w];
    cout<<endl;
 }
 if(choose == 4)
 break;
}

return 0;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!