#include <stdio.h>
#include <string.h>
#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
#define TRUE 1
#define FALSE 0
#define INFINITY 999 /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int PathMatrix2[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef int DistanceMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
}MGraph;
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
void CreateDN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造有向网G */
int i,j,k,w;
VertexType va,vb;
textcolor(4);
clrscr();
printf("please enter the amount of stations & ways in this form(vexnum,arcnum):");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("please enter the name of %d stations(<%d characters):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
}
printf("please enter the cost between two stations,in totle %d ways.example(v1 v2 100): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=w; /* 有向网 */
}
clrscr();
}
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=0;v<G.vexnum;++v)
{
final[v]=FALSE;
(*D)[v]=G.arcs[v0][v].adj;
for(w=0;w<G.vexnum;++w)
(*P)[v][w]=FALSE; /* 设空路径 */
if((*D)[v]<INFINITY)
{
(*P)[v][v0]=TRUE;
(*P)[v][v]=TRUE;
}
}
(*D)[v0]=0;
final[v0]=TRUE; /* 初始化,v0顶点属于S集 */
for(i=1;i<G.vexnum;++i) /* 其余G.vexnum-1个顶点 */
{ /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
min=INFINITY; /* 当前所知离v0顶点的最近距离 */
for(w=0;w<G.vexnum;++w)
if(!final[w]) /* w顶点在V-S中 */
if((*D)[w]<min)
{
v=w;
min=(*D)[w];
} /* w顶点离v0顶点更近 */
final[v]=TRUE; /* 离v0顶点最近的v加入S集 */
for(w=0;w<G.vexnum;++w) /* 更新当前最短路径及距离 */
{
if(!final[w]&&min<INFINITY&&G.arcs[v][w].adj<INFINITY&&(min+G.arcs[v][w].adj<(*D)[w]))
{ /* 修改D[w]和P[w],w∈V-S */
(*D)[w]=min+G.arcs[v][w].adj;
for(j=0;j<G.vexnum;++j)
(*P)[w][j]=(*P)[v][j];
(*P)[w][w]=TRUE;
}
}
}
}
void ShortestPath_FLOYD(MGraph G,PathMatrix2 *p,DistanceMatrix *D){
int v,w,u,i;
for(v=0;v<G.vexnum;++v)
for(w=0;w<G.vexnum;++w){
(*D)[v][w]=G.arcs[v][w].adj;
for(u=0;u<G.vexnum;++u)
if((*D)[v][w]<INFINITY){
(*p)[v][w][v]=TRUE;(*p)[v][w][w]=TRUE;
}
}
for(u=0;u<G.vexnum;++u)
for(v=0;v<G.vexnum;++v)
for(w=0;w<G.vexnum;++w)
if((*D)[v][u]+(*D)[u][w]<(*D)[v][w]){
(*D)[v][w]=(*D)[v][u]+(*D)[u][w];
for(i=0;i<G.vexnum;++i)
(*p)[v][w][i]=(*p)[v][u][i]||(*p)[u][w][i];
}
}
void menu()
{
printf("********************************************************************************");
printf("********************************************************************************");
printf("**1.please choose the shortest way from the certain station to every station **\n");
printf("**2.please choose the shortest way from the random two stations **\n");
printf("********************************************************************************");
printf("********************************************************************************");
}
void main()
{
int i,a,k=1,j,v0=0; /* v0为源点 */
MGraph g;
PathMatrix p;
PathMatrix2 p1;
ShortPathTable d;
DistanceMatrix d1;
CreateDN(&g);
while(k){
menu();
printf("choose:");
scanf("%d",&a);
switch(a)
{case 1:
ShortestPath_DIJ(g,v0,&p,&d);
printf("the shortest path :p[i][j]:\n");
for(i=0;i<g.vexnum;++i)
{
for(j=0;j<g.vexnum;++j)
printf("%2d",p[i][j]);
printf("\n");
}
printf("the cost from %s to every station is :\n",g.vexs[0]);
for(i=1;i<g.vexnum;++i)
printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);break;
case 2:
ShortestPath_FLOYD(g,&p1,&d1);
for(i=0;i<g.vexnum;++i)
{
printf("the cost from %s to every station is :\n",g.vexs[i]);
for(j=0;j<g.vexnum;++j)
if(g.vexs[i]!=g.vexs[j])
printf("%s-%s:%d\n",g.vexs[i],g.vexs[j],d1[i][j]);
}break;
}
printf("enter 1 to reback the menu.enter 0 to exit\n");
scanf("%d",&k);
}
}
