## 三维数组不知哪里有问题

/***********************************
*此程序功能是求50个顶点时，有三个点
*作为车站时的最短路径
***********************************/

#include <stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 51                             //矩阵大小51*51，a[0][i]与a[i][0]不用
#define TRUE 1
#define FALSE 0
#define INFINITY 32767                                //用整型最大值代替∞
typedef int VERTYPE;
///////////////////////////////////////////////////////
//mgraph数据结构
typedef struct
{
VERTYPE  vexs[MAX_VERTEX_NUM];                   //顶点向量
int      arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   //邻接矩阵
int      vexnum,arcnum;                          //图的当前顶点数和弧数
}mgraph, * MGraph;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

///////////////////////////////////////////////////////
//初始化图
void init_mgraph(MGraph &g)
{
g=(MGraph)malloc(sizeof(mgraph));
g->vexnum=50;  //初始顶点数位50
g->arcnum=0;  //初始弧数为0
for(int i=1;i<=g->vexnum;i++)
g->vexs[i]= i;

for(i=1;i<=g->vexnum;i++)
for(int j=1;j<=g->vexnum;j++)
g->arcs[i][j] = (i == j ?0:INFINITY);
//////////////////////////////////////////
//无向图由两部分构成，即A--->B的有向图和//
//B--->A的有向图                        //
//////////////////////////////////////////

/*下面首先构建A---->B的有向图*/
g->arcs[1][2]   = 400;
g->arcs[1][3]   = 450;
g->arcs[2][4]   = 300;
g->arcs[2][21]  = 230;
g->arcs[2][47]  = 140;
g->arcs[3][4]   = 600;
g->arcs[4][5]   = 210;
g->arcs[4][19]  = 310;
g->arcs[5][6]   = 230;
g->arcs[5][7]   = 200;
g->arcs[6][7]   = 320;
g->arcs[6][8]   = 340;
g->arcs[7][8]   = 170;
g->arcs[7][18]  = 160;
g->arcs[8][9]   = 200;
g->arcs[8][15]  = 285;
g->arcs[9][10]  = 180;
g->arcs[10][11] = 150;
g->arcs[10][15] = 160;
g->arcs[11][12] = 140;
g->arcs[11][14] = 130;
g->arcs[12][13] = 200;
g->arcs[13][34] = 400;
g->arcs[14][15] = 190;
g->arcs[14][26] = 190;
g->arcs[15][16] = 170;
g->arcs[15][17] = 250;
g->arcs[16][17] = 140;
g->arcs[16][18] = 130;
g->arcs[17][27] = 240;
g->arcs[18][19] = 204;
g->arcs[18][25] = 180;
g->arcs[19][20] = 140;
g->arcs[19][24] = 175;
g->arcs[20][21] = 180;
g->arcs[20][24] = 190;
g->arcs[21][22] = 300;
g->arcs[21][23] = 270;
g->arcs[21][47] = 350;
g->arcs[22][44] = 160;
g->arcs[22][45] = 270;
g->arcs[22][48] = 180;
g->arcs[23][24] = 240;
g->arcs[23][29] = 210;
g->arcs[23][30] = 290;
g->arcs[23][44] = 150;
g->arcs[24][25] = 170;
g->arcs[24][28] = 130;
g->arcs[26][27] = 140;
g->arcs[26][34] = 320;
g->arcs[27][28] = 190;
g->arcs[28][29] = 260;
g->arcs[29][31] = 190;
g->arcs[30][31] = 240;
g->arcs[30][42] = 130;
g->arcs[30][43] = 210;
g->arcs[31][32] = 230;
g->arcs[31][36] = 260;
g->arcs[31][50] = 210;
g->arcs[32][33] = 190;
g->arcs[32][35] = 140;
g->arcs[32][36] = 240;
g->arcs[33][34] = 210;
g->arcs[35][37] = 160;
g->arcs[36][39] = 180;
g->arcs[36][40] = 190;
g->arcs[37][38] = 135;
g->arcs[38][39] = 130;
g->arcs[39][41] = 310;
g->arcs[40][41] = 140;
g->arcs[40][50] = 190;
g->arcs[42][50] = 200;
g->arcs[43][44] = 260;
g->arcs[43][45] = 210;
g->arcs[45][46] = 240;
g->arcs[46][48] = 280;
g->arcs[48][49] = 200;
/*构建B---->A的有向图*/
g->arcs[2][1]   = 400;
g->arcs[3][1]   = 450;
g->arcs[4][2]   = 300;
g->arcs[21][2]  = 230;
g->arcs[47][2]  = 140;
g->arcs[4][3]   = 600;
g->arcs[5][4]   = 210;
g->arcs[19][4]  = 310;
g->arcs[6][5]   = 230;
g->arcs[7][5]   = 200;
g->arcs[7][6]   = 320;
g->arcs[8][6]   = 340;
g->arcs[8][7]   = 170;
g->arcs[18][7]  = 160;
g->arcs[9][8]   = 200;
g->arcs[15][8]  = 285;
g->arcs[10][9]  = 180;
g->arcs[11][10] = 150;
g->arcs[15][10] = 160;
g->arcs[12][11] = 140;
g->arcs[14][11] = 130;
g->arcs[13][12] = 200;
g->arcs[34][13] = 400;
g->arcs[15][14] = 190;
g->arcs[26][14] = 190;
g->arcs[16][15] = 170;
g->arcs[17][15] = 250;
g->arcs[17][16] = 140;
g->arcs[18][16] = 130;
g->arcs[27][17] = 240;
g->arcs[19][18] = 204;
g->arcs[25][18] = 180;
g->arcs[20][19] = 140;
g->arcs[24][19] = 175;
g->arcs[21][20] = 180;
g->arcs[24][20] = 190;
g->arcs[22][21] = 300;
g->arcs[23][21] = 270;
g->arcs[47][21] = 350;
g->arcs[44][22] = 160;
g->arcs[45][22] = 270;
g->arcs[48][22] = 180;
g->arcs[24][23] = 240;
g->arcs[29][23] = 210;
g->arcs[30][23] = 290;
g->arcs[44][23] = 150;
g->arcs[25][24] = 170;
g->arcs[28][24] = 130;
g->arcs[27][26] = 140;
g->arcs[34][26] = 320;
g->arcs[28][27] = 190;
g->arcs[29][28] = 260;
g->arcs[31][29] = 190;
g->arcs[31][30] = 240;
g->arcs[42][30] = 130;
g->arcs[43][30] = 210;
g->arcs[32][31] = 230;
g->arcs[36][31] = 260;
g->arcs[50][31] = 210;
g->arcs[33][32] = 190;
g->arcs[35][32] = 140;
g->arcs[36][32] = 240;
g->arcs[34][33] = 210;
g->arcs[37][35] = 160;
g->arcs[39][36] = 180;
g->arcs[40][36] = 190;
g->arcs[38][37] = 135;
g->arcs[39][38] = 130;
g->arcs[41][39] = 310;
g->arcs[41][40] = 140;
g->arcs[50][40] = 190;
g->arcs[50][42] = 200;
g->arcs[44][43] = 260;
g->arcs[45][43] = 210;
g->arcs[46][45] = 240;
g->arcs[48][46] = 280;
g->arcs[49][48] = 200;
}

///////////////////////////////////////////////////////
//Dijkstra算法
void ShortestPath_DIJ(MGraph &g, int v0, PathMatrix *P, ShortPathTable *D)
{   // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
// 若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。
// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
int v,w,i,j,min;
int final[MAX_VERTEX_NUM];
for(v=1; v<=g->vexnum; ++v)
{
final[v] = FALSE;
(*D)[v] = g->arcs[v0][v];
for(w=1; w<=g->vexnum; ++w)
(*P)[v][w] = FALSE;        //设空路径
if((*D)[v] < INFINITY)         //v0可以直接到达的点v
{
(*P)[v][v0] = TRUE;        //v0是v0直接到达v的路径的始点
(*P)[v][v] = TRUE;         //v是v0直接到达v的路径的终点
}
}
(*D)[v0] = 0;
final[v0] = TRUE;    //初始化，v0顶点属于S集
//开始主循环，每次求得v0到某个v顶点的最短路径，并加入v到S集
for(i=1; i<g->vexnum; i++)    //其余g.vexnum-1个顶点
{
min=INFINITY;             //当前所知离v0顶点的最近距离
for(w=1; w<=g->vexnum; w++)
{
if(!final[w] && (*D)[w]<min) //w顶点在V-S中
{
v=w;
min = (*D)[w];           //w顶点离v0顶点更近
}
}
final[v] = TRUE;                 //离v0顶点最近的v加入S集
for(w=1; w<=g->vexnum; w++)
{   //更新当前最短路径及距离
if(!final[w] && (min+g->arcs[v][w]<(*D)[w])) //如果经过v顶点的路径比现在这条路径的长度短的话
{   // 修改D[w]和P[w],w∈V-S
(*D)[w] = min + g->arcs[v][w];           //修改当前路径长度
for(j=1;j<=g->vexnum;++j)
(*P)[w][j]=(*P)[v][j];               //将经过v点的路径复制过来
(*P)[w][w]=TRUE;                         //最后的重点为TURE
}
}
}
}

///////////////////////////////////////////////////////
//main主函数
void main()
{   int i, j, k, l;
int num = 0;              //num用于换行
MGraph G;
init_mgraph(G);           //初始化图
PathMatrix P[51];         //p[0]不用
ShortPathTable D[51];     //求某点到其余各点的最短路径，D[0]不用
int v[51];                //v[0]不用
for(i=1;i<=G->vexnum;++i) //求50个点到其余个点的最短距离
{
v[i] = i;
ShortestPath_DIJ(G, v[i], &P[i], &D[i]);
}

printf("各源点到各顶点的最短路径长度矩阵如下:\n");
for(i=1;i<=G->vexnum;++i)
{
printf("%d    ", i);
for(j=1;j<=G->vexnum;++j)
printf("%-4d ", D[i][j]);
printf("\n");
}
/*********************************
*这个程序从这里开始就有问题了，
*但是不知道这个三维数组加到里
*面后，为什么就有问题？
*********************************/
int min;
int sum[51][51][51];

for(i=1;i<=G->vexnum-2;++i)
for(j=i+1;j<=G->vexnum-1;++j)
for(k=j+1;k<=G->vexnum;++k)
sum[i][j][k] = 0;

for(i=1;i<=G->vexnum-2;++i)
for(j=i+1;j<=G->vexnum-1;++j)
for(k=j+1;k<=G->vexnum;++k)
for(l=1;l<=G->vexnum;++l)
{
min = (((D[i][l]<D[j][l]) ? D[i][l]:D[j][l]) < D[k][l]) ? ((D[i][l]<D[j][l]) ? D[i][l]:D[j][l]) : D[k][l];
sum[i][j][k] += min;
}

int MIN = sum[1][2][3];
for(i=1;i<=G->vexnum-2;++i)
for(j=i+1;j<=G->vexnum-1;++j)
for(k=j+1;k<=G->vexnum;++k)
if(MIN > sum[i][j][k])
MIN = sum[i][j][k];

printf("\n最短距离：%d", MIN);
for(i=1;i<=G->vexnum-2;++i)
for(j=i+1;j<=G->vexnum-1;++j)
for(k=j+1;k<=G->vexnum;++k)
if(MIN == sum[i][j][k])
{
printf("\ni=%d,j=%d,k=%d\n", i, j, k);
break;
}
}

### 以下是问题补充：

@鹏城二少：错误在main中，里面的那个三位数组有问题，但不知道哪里有问题，求大哥大姐指出！感激不尽！ (2012/05/24 16:54)
@鹏城二少：错误在main中，里面的那个三位数组有问题，但不知道哪里有问题，求大哥大姐指出！感激不尽！ (2012/05/24 16:54)

0