
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 44
#define MAXLEN 44
typedef int VertexType;
typedef int ArcType;
typedef struct
{
VertexType vexs[MaxSize];
ArcType arcs[MaxSize][MaxSize];
int vexnum;
int arcnum;
}AdjMatrix;
#define MAXCOST 32767
void jiemian()
{
one: printf("\t\t\t********************************\n");
printf("\t\t\t********************************\n");
printf("\t\t\t*校园卡三点位置问题(c++版实现) *\n");
printf("\t\t\t* *\n");
printf("\t\t\t* 李火林&赵亚*\n");
printf("\t\t\t********************************\n");
printf("\t\t\t********************************\n");
printf("\n");
printf("\n");
printf("\n");
printf("\t\t\t\t请按ENTER进入...... \n");
if(getchar() != '\n')
{
system("cls");
fflush(stdin);
goto one;
}
system("cls");
}
void CreatMGraph(AdjMatrix *G)//初始化函数
{
int i;
int j;
G->vexnum=28;
G->arcnum=44;
for(i=0;i<G->vexnum ;i++)
{
G->vexs [i] = i;
}
for(i=0;i<G->vexnum ;i++)
for(j=0;j<G->vexnum ;j++)
G->arcs [i][j]=100;
G->arcs [0][1]=4;G->arcs [5][7]=5;
G->arcs [0][3]=4;G->arcs [6][7]=6;
G->arcs [1][2]=3;G->arcs [6][9]=5;
G->arcs [1][3]=4;G->arcs [7][8]=4;
G->arcs [1][4]=4;G->arcs [7][9]=4;
G->arcs [2][4]=6;G->arcs [8][10]=4;
G->arcs [2][5]=7; G->arcs [8][9]=4;
G->arcs [3][4]=3;G->arcs [9][10]=4;
G->arcs [3][6]=5;G->arcs [9][11]=5;
G->arcs [4][5]=6;G->arcs [10][12]=3;
G->arcs [4][6]=4;G->arcs [10][13]=6;
G->arcs[6][11]=7;G->arcs[10][11]=6;
/************************************/
G->arcs [11][13]=4;G->arcs [18][23]=4;
G->arcs [11][14]=6;G->arcs [19][20]=3;
G->arcs [12][15]=3;G->arcs [20][21]=3;
G->arcs [13][14]=8;G->arcs [21][22]=3;
G->arcs [13][15]=6;G->arcs [22][23]=5;
G->arcs [14][17]=7;G->arcs[22][27]=5;
G->arcs [14][24]=10;G->arcs [23][24]=4;
G->arcs [15][16]=3;G->arcs [24][25]=8;
G->arcs [16][19]=3;G->arcs [25][26]=5;
G->arcs [17][18]=2;G->arcs [26][27]=6;
G->arcs [18][19]=6;
/***************************************/
G->arcs [1][0]=4;G->arcs [7][5]=5;
G->arcs [3][0]=4;G->arcs [7][6]=6;
G->arcs [2][1]=3;G->arcs [9][6]=5;
G->arcs [3][1]=4;G->arcs [8][7]=4;
G->arcs [4][1]=4;G->arcs [9][7]=4;
G->arcs [4][2]=6;G->arcs [10][8]=4;
G->arcs [5][2]=7; G->arcs [9][8]=4;
G->arcs [4][3]=3;G->arcs [10][9]=4;
G->arcs [6][3]=5;G->arcs [11][9]=5;
G->arcs [5][4]=6;G->arcs [12][10]=3;
G->arcs [6][4]=4;G->arcs [13][10]=6;
G->arcs[11][6]=7;G->arcs[11][10]=6;
/************************************/
G->arcs [13][11]=4;G->arcs [23][18]=4;
G->arcs [14][11]=6;G->arcs [20][19]=3;
G->arcs [15][12]=3;G->arcs [21][20]=3;
G->arcs [14][13]=8;G->arcs [22][21]=3;
G->arcs [15][13]=6;G->arcs [23][22]=5;
G->arcs [17][14]=7;G->arcs[27][22]=5;
G->arcs [24][14]=10;G->arcs [24][23]=4;
G->arcs [16][15]=3;G->arcs [25][24]=8;
G->arcs [19][16]=3;G->arcs [26][25]=5;
G->arcs [18][17]=2;G->arcs [27][26]=6;
G->arcs [19][18]=6;
}
//实现任意两点的最短路径。
int* shortpath_dijkstra(AdjMatrix *G,int distance[],int x)
{
int cost[MAXLEN][MAXLEN];
int path[MAXLEN];
int s[MAXLEN];
int i,j,v0,min,u;
v0=x;
for(i=0; i<G->vexnum; i++)
for(j=0; j<G->vexnum; j++)
cost[i][j]=G->arcs[i][j];
for(i=0; i<G->vexnum; i++){
distance[i]=cost[v0][i];
if(distance[i]<32767&&distance[i]>0) path[i]=v0;
s[i]=0;
}
s[v0]=1;
for(i=1; i<G->vexnum; i++){
min=32767;
u=v0;
for(j=0;j<G->vexnum;j++)
if(s[j]==0&&distance[j]<min)
{min=distance[j]; u=j;}
s[u]=1;
for(j=0; j<G->vexnum; j++)
if(s[j]==0&&distance[u]+cost[u][j]<distance[j]){
distance[j]=distance[u]+cost[u][j];
path[j]=u;
}
}
for(i=0;i<G->vexnum;i++)
if(s[i]==1){
u=i;
return distance;
}
//else printf("%4d<-%4c:无路径\n",G->vexs[i], G->vexs[v0]);
return distance;
}
//具体实现三点之间的最短路径。
void panduan(AdjMatrix *G)
{
int i,j,k,a,d,g,f;
int m[MAXLEN],s[MAXLEN],n[MAXLEN];
int sum1,sum2,sum3,sum4;
int min[100]={32767};
int b[100]={0};
int c[100]={0};
int e[100]={0};
f=0;
start:printf("\t\t\t*****************************\n");
printf("\t\t\t*准备计算请按enter确认......*\n");
printf("\t\t\t*****************************\n");
if(getchar() != '\n')
{
system("cls");
fflush(stdin);
goto start;
}
for(i=0;i<28;i++)
for(j=i+1;j<28;j++)
for(k=j+1;k<28;k++)
{
shortpath_dijkstra(G,m,i);
shortpath_dijkstra(G,s,j);
shortpath_dijkstra(G,n,k);
m[i]=0;
s[j]=0;
n[k]=0;
for(a=0;a<28;a++)
{
if(m[a] > s[a]||m[a] > n[a])
{
m[a]=0;
if(s[a] > n[a])
s[a]=0;
else
n[a]=0;
}
else
{
s[a] = 0;
n[a] = 0;
}
}
for(d=0,sum1=0,sum2=0,sum3=0,sum4=0;d<28;d++)
{
sum1 = m[d]+sum1;
sum2 = s[d]+sum2;
sum3 = n[d]+sum3;
sum4 = sum1+sum2+sum3;
}
// for(d=0;d<28;d++)
printf("(%d,%d,%d),%d\n",i,j,k,sum4);
if(min[f]>=sum4)
{
min[f]=sum4;
b[f]=i;
c[f]=j;
e[f]=k;
f++;
min[f]=sum4;
}
}
system("cls");
printf("\t\t\t*****************************\n");
printf("\t\t\t*最短路径的顶点位置和总权值:*\n");
for(g=f-1;g>=0;g--)
{
if(min[g]==min[f-1])
{
printf("\t\t\t*位置:(%d,%d,%d)路径:%d *\n",b[g],c[g],e[g],min[g]);
}
}
printf("\t\t\t*****************************\n");
}
int main(int argc,char **argv)
{
// int i;
// int j;
// int close[100];
AdjMatrix G;
jiemian();
CreatMGraph(&G);
/* for(i=0;i<28;i++)
{
printf("%d,",i);
}
printf("\n");
for(i=0;i<G.vexnum ;i++)
{
printf("%d",G.vexs [i]);
for(j=0;j<G.vexnum ;j++)
printf("%d",G.arcs [i][j]);
printf("\n");
}*/
panduan(&G);
getchar();
}
#include<stdlib.h>
#define MaxSize 44
#define MAXLEN 44
typedef int VertexType;
typedef int ArcType;
typedef struct
{
VertexType vexs[MaxSize];
ArcType arcs[MaxSize][MaxSize];
int vexnum;
int arcnum;
}AdjMatrix;
#define MAXCOST 32767
void jiemian()
{
one: printf("\t\t\t********************************\n");
printf("\t\t\t********************************\n");
printf("\t\t\t*校园卡三点位置问题(c++版实现) *\n");
printf("\t\t\t* *\n");
printf("\t\t\t* 李火林&赵亚*\n");
printf("\t\t\t********************************\n");
printf("\t\t\t********************************\n");
printf("\n");
printf("\n");
printf("\n");
printf("\t\t\t\t请按ENTER进入...... \n");
if(getchar() != '\n')
{
system("cls");
fflush(stdin);
goto one;
}
system("cls");
}
void CreatMGraph(AdjMatrix *G)//初始化函数
{
int i;
int j;
G->vexnum=28;
G->arcnum=44;
for(i=0;i<G->vexnum ;i++)
{
G->vexs [i] = i;
}
for(i=0;i<G->vexnum ;i++)
for(j=0;j<G->vexnum ;j++)
G->arcs [i][j]=100;
G->arcs [0][1]=4;G->arcs [5][7]=5;
G->arcs [0][3]=4;G->arcs [6][7]=6;
G->arcs [1][2]=3;G->arcs [6][9]=5;
G->arcs [1][3]=4;G->arcs [7][8]=4;
G->arcs [1][4]=4;G->arcs [7][9]=4;
G->arcs [2][4]=6;G->arcs [8][10]=4;
G->arcs [2][5]=7; G->arcs [8][9]=4;
G->arcs [3][4]=3;G->arcs [9][10]=4;
G->arcs [3][6]=5;G->arcs [9][11]=5;
G->arcs [4][5]=6;G->arcs [10][12]=3;
G->arcs [4][6]=4;G->arcs [10][13]=6;
G->arcs[6][11]=7;G->arcs[10][11]=6;
/************************************/
G->arcs [11][13]=4;G->arcs [18][23]=4;
G->arcs [11][14]=6;G->arcs [19][20]=3;
G->arcs [12][15]=3;G->arcs [20][21]=3;
G->arcs [13][14]=8;G->arcs [21][22]=3;
G->arcs [13][15]=6;G->arcs [22][23]=5;
G->arcs [14][17]=7;G->arcs[22][27]=5;
G->arcs [14][24]=10;G->arcs [23][24]=4;
G->arcs [15][16]=3;G->arcs [24][25]=8;
G->arcs [16][19]=3;G->arcs [25][26]=5;
G->arcs [17][18]=2;G->arcs [26][27]=6;
G->arcs [18][19]=6;
/***************************************/
G->arcs [1][0]=4;G->arcs [7][5]=5;
G->arcs [3][0]=4;G->arcs [7][6]=6;
G->arcs [2][1]=3;G->arcs [9][6]=5;
G->arcs [3][1]=4;G->arcs [8][7]=4;
G->arcs [4][1]=4;G->arcs [9][7]=4;
G->arcs [4][2]=6;G->arcs [10][8]=4;
G->arcs [5][2]=7; G->arcs [9][8]=4;
G->arcs [4][3]=3;G->arcs [10][9]=4;
G->arcs [6][3]=5;G->arcs [11][9]=5;
G->arcs [5][4]=6;G->arcs [12][10]=3;
G->arcs [6][4]=4;G->arcs [13][10]=6;
G->arcs[11][6]=7;G->arcs[11][10]=6;
/************************************/
G->arcs [13][11]=4;G->arcs [23][18]=4;
G->arcs [14][11]=6;G->arcs [20][19]=3;
G->arcs [15][12]=3;G->arcs [21][20]=3;
G->arcs [14][13]=8;G->arcs [22][21]=3;
G->arcs [15][13]=6;G->arcs [23][22]=5;
G->arcs [17][14]=7;G->arcs[27][22]=5;
G->arcs [24][14]=10;G->arcs [24][23]=4;
G->arcs [16][15]=3;G->arcs [25][24]=8;
G->arcs [19][16]=3;G->arcs [26][25]=5;
G->arcs [18][17]=2;G->arcs [27][26]=6;
G->arcs [19][18]=6;
}
//实现任意两点的最短路径。
int* shortpath_dijkstra(AdjMatrix *G,int distance[],int x)
{
int cost[MAXLEN][MAXLEN];
int path[MAXLEN];
int s[MAXLEN];
int i,j,v0,min,u;
v0=x;
for(i=0; i<G->vexnum; i++)
for(j=0; j<G->vexnum; j++)
cost[i][j]=G->arcs[i][j];
for(i=0; i<G->vexnum; i++){
distance[i]=cost[v0][i];
if(distance[i]<32767&&distance[i]>0) path[i]=v0;
s[i]=0;
}
s[v0]=1;
for(i=1; i<G->vexnum; i++){
min=32767;
u=v0;
for(j=0;j<G->vexnum;j++)
if(s[j]==0&&distance[j]<min)
{min=distance[j]; u=j;}
s[u]=1;
for(j=0; j<G->vexnum; j++)
if(s[j]==0&&distance[u]+cost[u][j]<distance[j]){
distance[j]=distance[u]+cost[u][j];
path[j]=u;
}
}
for(i=0;i<G->vexnum;i++)
if(s[i]==1){
u=i;
return distance;
}
//else printf("%4d<-%4c:无路径\n",G->vexs[i], G->vexs[v0]);
return distance;
}
//具体实现三点之间的最短路径。
void panduan(AdjMatrix *G)
{
int i,j,k,a,d,g,f;
int m[MAXLEN],s[MAXLEN],n[MAXLEN];
int sum1,sum2,sum3,sum4;
int min[100]={32767};
int b[100]={0};
int c[100]={0};
int e[100]={0};
f=0;
start:printf("\t\t\t*****************************\n");
printf("\t\t\t*准备计算请按enter确认......*\n");
printf("\t\t\t*****************************\n");
if(getchar() != '\n')
{
system("cls");
fflush(stdin);
goto start;
}
for(i=0;i<28;i++)
for(j=i+1;j<28;j++)
for(k=j+1;k<28;k++)
{
shortpath_dijkstra(G,m,i);
shortpath_dijkstra(G,s,j);
shortpath_dijkstra(G,n,k);
m[i]=0;
s[j]=0;
n[k]=0;
for(a=0;a<28;a++)
{
if(m[a] > s[a]||m[a] > n[a])
{
m[a]=0;
if(s[a] > n[a])
s[a]=0;
else
n[a]=0;
}
else
{
s[a] = 0;
n[a] = 0;
}
}
for(d=0,sum1=0,sum2=0,sum3=0,sum4=0;d<28;d++)
{
sum1 = m[d]+sum1;
sum2 = s[d]+sum2;
sum3 = n[d]+sum3;
sum4 = sum1+sum2+sum3;
}
// for(d=0;d<28;d++)
printf("(%d,%d,%d),%d\n",i,j,k,sum4);
if(min[f]>=sum4)
{
min[f]=sum4;
b[f]=i;
c[f]=j;
e[f]=k;
f++;
min[f]=sum4;
}
}
system("cls");
printf("\t\t\t*****************************\n");
printf("\t\t\t*最短路径的顶点位置和总权值:*\n");
for(g=f-1;g>=0;g--)
{
if(min[g]==min[f-1])
{
printf("\t\t\t*位置:(%d,%d,%d)路径:%d *\n",b[g],c[g],e[g],min[g]);
}
}
printf("\t\t\t*****************************\n");
}
int main(int argc,char **argv)
{
// int i;
// int j;
// int close[100];
AdjMatrix G;
jiemian();
CreatMGraph(&G);
/* for(i=0;i<28;i++)
{
printf("%d,",i);
}
printf("\n");
for(i=0;i<G.vexnum ;i++)
{
printf("%d",G.vexs [i]);
for(j=0;j<G.vexnum ;j++)
printf("%d",G.arcs [i][j]);
printf("\n");
}*/
panduan(&G);
getchar();
}