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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
数据结构图最短路径基本程序
/*#include #include using namespace std; struct E{ int next; int c; }; vectoredge[101]; bool mark[101]; int Dis[101]; int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ if(n==0&&m==0)
数据结构与算法之最短路径--迪杰斯特拉算法
1 最短路径概念1.1 定义官方定义:对于内网图而言,最短路径是指两顶点之间经过的边上权值之和最小的路径。并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。由于非内网图没有边上的权值,所谓的最短路径其实是指两顶点之间经过的边数最少的路径。 1.2 对比最小生成树:能够保证整个拓扑图的所有路径之和最小,但不能保证任意两点之间是最短路径。 最短路径:是从一点出发,到达目的地的路径最小(到某顶点
【数据结构与算法】图之最短路径
8.6.1  最短路径的基本概念             在一个图中,若从一个结点到另一个结点存在着路径,定义路径长度为一条路径上所经过的边的数目。图中从一个结点到另一个结点可能存在着多条路径,我们把路径长度最短的那条路径叫做最短路径,其路径长度叫做最短路径长度或最短距离. 在一个带权图中,若从一个结点到另一个结点存在着一条路径,则称该路径上所经过边的权值之和为该路径上的带权路径长度。带权图中
数据结构:最短路径(Dijkstra c++实现)
#include #include #include #include using namespace std; #define MAXSIZE 10 //顶点最大个数 typedef string VertexType; //顶点类型 typedef int EdgeType; //权值类型,有向图(0,1),无向图(权值,无穷大) #define INFINITY 0xffff
数据结构与算法——最短路径Dijkstra算法的C++实现
数据结构与算法——最短路径Dijkstra算法的C++实现
C++代码,数据结构-最短路径(两种情况)(迪杰斯特拉算法和弗洛伊德算法)
1.单源的,从有向图某个源点, 到其他点的最短路径 利用算法迪杰斯特拉算法; Dijkstra算法的基本思想: 一个辅助数组D[max_v];每个D[i]表示当前所知源点到vi的最短路径的长度 一个辅助集合S,记录已找到最短路径的顶点的集合,他是逐步补充的;知道S集合包括所有点,起初S集合包含源点 1.先找出源点直接可达到顶点i,并把权记录到D[i]中,不可达到顶点记为最大值; 2.然
数据结构::迷宫(二)--栈的一个应用(求迷宫最短路径)
上篇文章我们知道求解迷宫通路的方法,但是一个迷宫有时是不止一条出路,在这些出路中,我们如何找到最短的那一条,这就是我今天要说的迷宫最短路径问题。 (此处使用的图): 【先来分析有什么解决方案:】 1、方法一:我们如果采用上章中递归的方式,将所走的路用2标记起来,此时如果找到一条路后,要进行回溯递归,但是到可以走的环中就出现问题了,说的有点迷糊是吧,我把图抛出来。 在这张图中
数据结构与算法12:单源最短路径Dijkstra算法
数据结构与算法12:单源最短路径Dijkstra算法     Dijkstra算法是一种经典的贪心算法例子。单源最短路径是指如何在一个图中,从某一点出发计算出这个点到其他点的最短距离。     Dijkstra算法的主要思想是贪心算法和松弛。计算中该算法不求一次得到某个点的最优解,而是给出一个该点距离的上界。通过不断降低上界的过程,使得最终达到最优解。该算法的主要步骤如下:
C语言数据结构顺序栈之迷宫求解最短路径
数据结构习题与解析(B级第3版) 李春葆 喻丹丹 编著 3.2
c语言实现求最短路径(迪杰斯特拉算法,《数据结构》算法7.15)
迪杰斯特拉算法从小到大的求出了从源点到其余各个点的最短路径,用到了邻接矩阵的储存结构。 代码如下:#include #define MAX_VERTEX_NUM 100 #define INFINITY 2000000000 typedef struct { int vexs[MAX_VERTEX_NUM]; int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];