校园导航问题.txt

数据结构课程设计,校园导航问题,一个比较简单的程序

#include "stdio.h"
#include<iostream.h>//输入输出
#include<conio.h>//输入输出
#define Max 999//路径不存在时，则用最大值代替
#define  VertexNum  10 //顶点数（景点数）
#define   EdgeNum  16 //边数（路径数）   
int Graph[VertexNum][VertexNum];//图  
intEdge[EdgeNum][3]={{0,1,160},{0,2,80},{0,3,80},{1,2,60},
    {1,4,100},{2,3,50},{3,5,40},{3,4,100},
    {4,5,110},{4,7,70},{5,7,50},{5,6,50},
                   {6,8,60},{7,8,50},{7,9,40},{8,9,90}};  //初始化边数组 
  int  Visited[VertexNum]; //记录浏览过的景点（ Visited 从英语语法都能猜到）
 int Distance[VertexNum];// 两景点的距离后面用到Distance[i]=Graph[Begin][i];即景点Begin到景点i的距离    
void   dijkstra(int   Begin)   
{   
int   MinEdge;   
int   Vertex;   
 int   i,j;   
 int   Edges;   
 Edges=1;   
 Visited[Begin]=1;//导航开始的地方   
for(i=1;i<VertexNum;i++)   
Distance[i]=Graph[Begin][i];  //将图的数据拷贝到距离Distance[Begin]=0; //？？？？？？？？？  
printf("Vertice");//景点   
 for(i=0;i<VertexNum;i++)   
printf("%5d",i); //输出矩阵的横坐标
printf("\n");   
printf("Step   %d:",Edges); //step 1  
for(i=0;i<VertexNum;i++)   
printf("%5d",Distance[i]); //step 1 那行的数据 （路径大小
printf("\n");   
while(Edges<(VertexNum))   
{   
Edges++;   
 MinEdge=Max; //将最大值999赋给最小的边  
 for(j=0;j<VertexNum;j++)   
 {   
        if(Visited[j]==0 && MinEdge>Distance[j])  //Visited[j]==0 应该表示没有浏览过的，开始并没有赋值默认为0 
 {   
Vertex=j; //  j表示浏览过的景点数
        MinEdge=Distance[j]; //  由MinEdge>Distance[j]可以看出应该是 将距离赋给边，
		                       //  因为MinEdge总是999表示开始的值，只有赋过值才表示有路径
}    
 }   
Visited[Vertex]=1;   
printf("Step   %d:",Edges);// Step 2 到Step10
for(j=0;j<VertexNum;j++)   
{   
    if(Visited[j]==0 && Distance[Vertex]+Graph[Vertex][j]<Distance[j])
			//应该理解为A到B加上B到C的距离  比  A直接到C的距离短   
{   
               Distance[j]=Distance[Vertex]+Graph[Vertex][j]; //将最小距离保存到Distance[ ]中  
}   
           printf("%5d",Distance[j]);//距离矩阵图 （中间那块的数字即Step 右边那一片）  
}   
 printf("\n");   
}   
}   
void   Print_M_Graph() //打印输出图  
 {   
int   i,j;   
 printf("Vertice");   
 for(i=1;i<VertexNum;i++)   
{   
printf("\n");   
for(j=1;j<VertexNum;j++)   
                  printf("%5d",Graph[i][j]);//以矩阵方式打印输出图包含路径值，999除外   
printf("\n");   
 }   
 }   
    
          void   Create_M_Graph(int   Vertice1,int   Vertice2,int   Weight) //传入参数为两个顶点及它们间的距离
{   
    Graph[Vertice1][Vertice2]=Weight; //给两点赋权值 
}   
    
void   main()   
{   
 int   BeginVertex=1;   
 int   i,j;   
for(i=0;i<VertexNum;i++)   
Visited[i]=0;//初始化景点矩阵
for(i=0;i<VertexNum;i++)   
for(j=0;j<VertexNum;j++)   
 Graph[i][j]=Max;////初始化图各点为999
for(i=0;i<EdgeNum;i++) 
 Create_M_Graph(Edge[i][0],Edge[i][1],Edge[i][2]); //将开始的那一堆数据传如函数，即下面的数 
	   /*{{0,1,160},{0,2,80},{0,3,80},{1,2,60},
    {1,4,100},{2,3,50},{3,5,40},{3,4,100},
                      {4,5,110},{4,7,70},{5,7,50},{5,6,50},                                                             
                      {6,8,60},{7,8,50},{7,9,40},{8,9,90}};*/                                                  
 printf("##Graph##\n");   
Print_M_Graph();   
 printf("dijkstra   Algorthm   :\n");//dijkstra  算法   
 dijkstra(BeginVertex);  
getch();
}