netlen.c

单片机程序设计基础 随书光盘

//网络中顶点间最短距离算法（利用邻接矩阵）。
//
//网络结构：
//              A
//            / | \
//        4 /   |   \ 7
//        /     |     \
//      B      6|       C
//      | \ 9   |   8 / |
//      |   \   |   /   |
//      |     \ | /     |
//     8|       D       |5
//      |     / | \ 3   | 
//      |  5/   |   \   | 
//      | /     |     \ | 
//      E      4|       F 
//       \      |      /
//         \    |    /  
//        2  \  |  / 9
//              G
//
//从节点A出发的最短距离与路径：
//              A
//            / | \
//        4 /   |   \ 7
//        /     |     \
//      B=4    6|      C=7
//              |        
//              |        
//              |        
//             D=6         
//            / | \ 3     
//         5/   |   \     
//        /     |     \   
//      E=11   4|     F=9
//              |       
//              |       
//              |     
//             G=10
//
//从节点B出发的最短距离与路径：
//             A=4
//            /   \
//        4 /       \ 7
//        /           \
//      B             C=11
//      | \ 9            
//      |   \            
//      |     \          
//     8|      D=9         
//      |         \ 3     
//      |           \     
//      |             \   
//     E=8            F=12
//       \             
//         \            
//        2  \        
//           G=10
//
//从节点C出发的最短距离与路径：
//             A=7
//            /   \
//        4 /       \ 7
//        /           \
//      B=11            C
//                  8 / |
//                  /   |
//                /     |
//             D=8      |5
//            / |       | 
//         5/   |       | 
//        /     |       | 
//      E=13   4|      F=5 
//              |       
//              |       
//              |     
//             G=12
//
//从节点D出发的最短距离与路径：
//             A=6
//              |  
//              |      
//              |      
//      B=9    6|     C=8
//        \ 9   |   8 /  
//          \   |   /    
//            \ | /      
//              D         
//            / | \ 3     
//         5/   |   \     
//        /     |     \   
//      E=5    4|     F=3
//              |       
//              |       
//              |     
//             G=4
//
//
//从节点E出发的最短距离与路径：
//             A=11
//              |  
//              |      
//              |      
//     B=8     6|     C=13
//      |       |   8 /  
//      |       |   /    
//      |       | /      
//     8|      D=5         
//      |     /   \ 3     
//      |  5/       \     
//      | /           \   
//      E             F=8
//       \              
//         \            
//        2  \        
//            G=2
//
//
//从节点F出发的最短距离与路径：
//             A=9
//              |   
//              |      
//              |      
//      B=12   6|      C=5
//        \ 9   |       |
//          \   |       |
//            \ |       |
//             D=3      |5
//            / | \ 3   | 
//         5/   |   \   | 
//        /     |     \ | 
//      E=8    4|       F 
//              |       
//              |       
//              |    
//             G=7
//
//
//从节点G出发的最短距离与路径：
//             A=10
//              |  
//              |      
//              |      
//     B=10    6|     C=12
//      |       |   8 /  
//      |       |   /    
//      |       | /      
//     8|      D=4      
//      |       | \ 3     
//      |       |   \     
//      |       |     \   
//     E=2     4|     F=7
//       \      |       
//         \    |       
//        2  \  |     
//              G
//

#define N  7  //图的顶点数
#define MAX 9999  //一个远大于距离的数
char DOT[N]={'A','B','C','D','E','F','G'};//存放顶点信息的数组
char visited[N];	//存放顶点被访问标志
int  len[N];		//距离数组
char  F[N];		//父节点

//网络的邻接矩阵（MAX表示不相邻）:
int NET[N][N] ={{0,4,7,6,MAX,MAX,MAX},
		{4,0,MAX,9,8,MAX,MAX},
		{7,MAX,0,8,MAX,5,MAX},
		{6,9,8,0,5,3,4},
		{MAX,8,MAX,5,0,MAX,2},
		{MAX,MAX,5,3,MAX,0,9},
		{MAX,MAX,MAX,4,2,9,0}};

void MINLEN ( int k ) //计算各个顶点到序号为k的顶点的最短距离
{
	int i,j,p,min;
	for (i=0;i<N;i++) visited[i]=0;//初始化“已处理”标志
	visited[k] = 1 ; //首先设置序号为k的顶点为已处理
	for (i=0;i<N;i++) F[i] = (i==k)?'*':DOT[k] ;	//初始化父节点
	for (i=0;i<N;i++) len[i] = NET[k][i] ;	//初始化距离数组
	for (i=0;i<N-1;i++) {  //处理其它N-1个顶点
		min=MAX;p=-1;  //寻找最近的顶点
		for (j=0;j<N;j++) if (!visited[j] && len[j] <min ){
			min = len[j] ; p = j ;
			}
		visited[p] = 1 ; //设置该顶点为已处理
		for (j=0;j<N;j++) //调整其它顶点的最短距离
			if ( !visited[j] && NET[j][p]+len[p] < len[j] ) {
				len[j]=NET[j][p]+len[p];//更短的距离
				F[j]=DOT[p];  //新的父节点
				}
		}
}

main ( )
{
	int  i,j;
	for (i=0;i<N;i++)
		MINLEN (i) ; //计算各个顶点到序号为k的顶点的最短距离
	while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果 
}