//網(wǎng)絡(luò)中頂點間最短距離算法（利用鄰接矩陣）。
//
//網(wǎng)絡(luò)結(jié)構(gòu)：
//              A
//            / | \
//        4 /   |   \ 7
//        /     |     \
//      B      6|       C
//      | \ 9   |   8 / |
//      |   \   |   /   |
//      |     \ | /     |
//     8|       D       |5
//      |     / | \ 3   | 
//      |  5/   |   \   | 
//      | /     |     \ | 
//      E      4|       F 
//       \      |      /
//         \    |    /  
//        2  \  |  / 9
//              G
//
//從節(jié)點A出發(fā)的最短距離與路徑：
//              A
//            / | \
//        4 /   |   \ 7
//        /     |     \
//      B=4    6|      C=7
//              |        
//              |        
//              |        
//             D=6         
//            / | \ 3     
//         5/   |   \     
//        /     |     \   
//      E=11   4|     F=9
//              |       
//              |       
//              |     
//             G=10
//
//從節(jié)點B出發(fā)的最短距離與路徑：
//             A=4
//            /   \
//        4 /       \ 7
//        /           \
//      B             C=11
//      | \ 9            
//      |   \            
//      |     \          
//     8|      D=9         
//      |         \ 3     
//      |           \     
//      |             \   
//     E=8            F=12
//       \             
//         \            
//        2  \        
//           G=10
//
//從節(jié)點C出發(fā)的最短距離與路徑：
//             A=7
//            /   \
//        4 /       \ 7
//        /           \
//      B=11            C
//                  8 / |
//                  /   |
//                /     |
//             D=8      |5
//            / |       | 
//         5/   |       | 
//        /     |       | 
//      E=13   4|      F=5 
//              |       
//              |       
//              |     
//             G=12
//
//從節(jié)點D出發(fā)的最短距離與路徑：
//             A=6
//              |  
//              |      
//              |      
//      B=9    6|     C=8
//        \ 9   |   8 /  
//          \   |   /    
//            \ | /      
//              D         
//            / | \ 3     
//         5/   |   \     
//        /     |     \   
//      E=5    4|     F=3
//              |       
//              |       
//              |     
//             G=4
//
//
//從節(jié)點E出發(fā)的最短距離與路徑：
//             A=11
//              |  
//              |      
//              |      
//     B=8     6|     C=13
//      |       |   8 /  
//      |       |   /    
//      |       | /      
//     8|      D=5         
//      |     /   \ 3     
//      |  5/       \     
//      | /           \   
//      E             F=8
//       \              
//         \            
//        2  \        
//            G=2
//
//
//從節(jié)點F出發(fā)的最短距離與路徑：
//             A=9
//              |   
//              |      
//              |      
//      B=12   6|      C=5
//        \ 9   |       |
//          \   |       |
//            \ |       |
//             D=3      |5
//            / | \ 3   | 
//         5/   |   \   | 
//        /     |     \ | 
//      E=8    4|       F 
//              |       
//              |       
//              |    
//             G=7
//
//
//從節(jié)點G出發(fā)的最短距離與路徑：
//             A=10
//              |  
//              |      
//              |      
//     B=10    6|     C=12
//      |       |   8 /  
//      |       |   /    
//      |       | /      
//     8|      D=4      
//      |       | \ 3     
//      |       |   \     
//      |       |     \   
//     E=2     4|     F=7
//       \      |       
//         \    |       
//        2  \  |     
//              G
//

#define N  7  //圖的頂點數(shù)
#define MAX 9999  //一個遠大于距離的數(shù)
char DOT[N]={'A','B','C','D','E','F','G'};//存放頂點信息的數(shù)組
char visited[N];	//存放頂點被訪問標志
int  len[N];		//距離數(shù)組
char  F[N];		//父節(jié)點

//網(wǎng)絡(luò)的鄰接矩陣（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 ; //首先設(shè)置序號為k的頂點為已處理
	for (i=0;i<N;i++) F[i] = (i==k)?'*':DOT[k] ;	//初始化父節(jié)點
	for (i=0;i<N;i++) len[i] = NET[k][i] ;	//初始化距離數(shù)組
	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 ; //設(shè)置該頂點為已處理
		for (j=0;j<N;j++) //調(diào)整其它頂點的最短距離
			if ( !visited[j] && NET[j][p]+len[p] < len[j] ) {
				len[j]=NET[j][p]+len[p];//更短的距離
				F[j]=DOT[p];  //新的父節(jié)點
				}
		}
}

main ( )
{
	int  i,j;
	for (i=0;i<N;i++)
		MINLEN (i) ; //計算各個頂點到序號為k的頂點的最短距離
	while (1) ; //在這一行設(shè)置斷點,中止程序運行,以便觀察程序運行的結(jié)果 
}