C语言编程

#include #include

#define MVNum 100//最大顶点数 #define Maxint 32767

enum boolean{FALSE,TRUE}; typedef char VertexType; typedef int Adjmatrix;

typedef struct{

VertexType vexs[MVNum];//顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，假定为int型 Adjmatrix time[MVNum][MVNum]; Adjmatrix cost[MVNum][MVNum]; }MGraph;

int D1[MVNum],P1[MVNum];

int D[MVNum][MVNum],P[MVNum][MVNum];

void CreateMGraph(MGraph *G,int n,int e); void Dijkstra(MGraph *G,int v1,int n); void Floyd(MGraph *G,int n);

void Dijkstime(MGraph *G,int v1,int n); void Flotime(MGraph *G,int n);

void Dijkscost(MGraph *G,int v1,int n); void Flocost(MGraph *G,int n);

void CreateMGraph(MGraph *G,int n,int e)

{//采用邻接矩阵表示法构造有向图G，n、e标示图的当前定点数和边数 int i,j,k,w,a,b; for(i=1;i<=n;i++)//输入顶点信息 G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint;//初始化邻接矩阵 printf(\"输入%d条边的i,j,w,a,b：\\n\ for(k=1;k<=e;k++){ //读入e条边，建立邻接矩阵 scanf(\"%d,%d,%d,%d,%d\ G->arcs[i][j]=w; G->time[i][j]=a; G->cost[i][j]=b; /*G->arcs[i][j]=a; G->arcs[i][j]=b;*/ } printf(\"有向图的存储结构建立完毕！ \\n\"); }//建立有向图的存储结构

void Dijkstra(MGraph *G,int v1,int n)

{ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径p[v]及其权D[v] //设G是有向图的邻接矩阵，若边不存在，则G[i][j]= Maxint //S[v]为真当且仅当v属于S，即已求从v1到v的最短路径 int D2[MVNum],P2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v<=n;v++){//初始化S和D S[v]=FALSE;//置空最短路径终点集

D2[v]=G->arcs[v1][v];//置初始的最短路径值 if(D2[v]arcs[v][w])){//修改D2[w]和P2[w]，w属于V-S D2[w]=D2[v]+G->arcs[v][w]; P2[w]=v; } } printf(\"路径长度 路径\\n\"); for(i=1;i<=n;i++){ printf(\"%5d\ printf(\"%5d\ v=P2[i]; while(v!=0){ printf(\"<-%d\ v=P2[v]; } printf(\"\\n\"); } }

void Dijkstime(MGraph *G,int v1,int n)

{ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最少时间p[v]及其权D[v] //设G是有向图的邻接矩阵，若边不存在，则G[i][j]= Maxint //S[v]为真当且仅当v属于S，即已求从v1到v的最少时间 int D3[MVNum],P3[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v<=n;v++){//初始化S和D S[v]=FALSE;//置空最短路径终点集

D3[v]=G->time[v1][v];//置初始的最少时间值 if(D3[v]time[v][w])){//修改D2[w]和P2[w]，w属于V-S D3[w]=D3[v]+G->time[v][w]; P3[w]=v; } } printf(\"时间花费 时间\\n\"); for(i=1;i<=n;i++){ printf(\"%5d\ printf(\"%5d\ v=P3[i]; while(v!=0){ printf(\"<-%d\ v=P3[v]; } printf(\"\\n\"); } }

void Dijkscost(MGraph *G,int v1,int n)

{ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最少花费p[v]及其权D[v] //设G是有向图的邻接矩阵，若边不存在，则G[i][j]= Maxint //S[v]为真当且仅当v属于S，即已求从v1到v的最少花费

int D2[MVNum],P2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v<=n;v++){//初始化S和D S[v]=FALSE;//置空最少花费终点集

D2[v]=G->cost[v1][v];//置初始的最最少花费 if(D2[v]cost[v][w])){//修改D2[w]和P2[w]，w属于V-S D2[w]=D2[v]+G->cost[v][w]; P2[w]=v; } } printf(\"花费多少 花费\\n\"); for(i=1;i<=n;i++){ printf(\"%5d\ printf(\"%5d\ v=P2[i]; while(v!=0){ printf(\"<-%d\ v=P2[v]; } printf(\"\\n\"); } }

void Floyd(MGraph *G,int n) {

int i,j,k;

for(i=1;i<=n;i++)//设置路径长度D和路径path初值 for(j=1;j<=n;j++) {

if(G->arcs[i][j]!=Maxint) P[i][j]=j;//j是i的后继 else P[i][j]=0; D[i][j]=G->arcs[i][j]; } for(k=1;k<=n;k++) { //做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上 for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]void Flotime(MGraph *G,int n) {

int i,j,k;

for(i=1;i<=n;i++)//设置时间长度D和时间path初值 for(j=1;j<=n;j++) { if(G->time[i][j]!=Maxint) P[i][j]=j;//j是i的后继 else P[i][j]=0; D[i][j]=G->time[i][j]; } for(k=1;k<=n;k++) { //做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最少时间Pij上 for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]void Flocost(MGraph *G,int n) {

int i,j,k;

for(i=1;i<=n;i++)//设置花费长度D和花费path初值 for(j=1;j<=n;j++) { if(G->cost[i][j]!=Maxint) P[i][j]=j;//j是i的后继 else P[i][j]=0; D[i][j]=G->cost[i][j]; } for(k=1;k<=n;k++) { //做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最少花费Pij上 for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]void main() {

MGraph *G; int n,e,v,w,k; int xz=1;

G=(MGraph*)malloc(sizeof(MGraph));

printf(\"输入图中顶点个数和边数n，e： \"); scanf(\"%d,%d\

CreateMGraph(G,n,e);//建立图的存储结构 while(1) { printf(\"********交通咨询问题的实现***********\\n\"); printf(\"********关于城市之间的最少问题*******\\n\"); printf(\"===================================\\n\"); printf(\"1.求一个城市到所有城市的最短路径\\n\"); printf(\"2.求任意的两个城市之间的最短路径\\n\"); printf(\"3.求一个城市到所有城市的最短时间\\n\"); printf(\"4.求任意的两个城市之间的最短时间\\n\");

printf(\"5.求一个城市到所有城市的最少花费\\n\"); printf(\"6.求任意的两个城市之间的最少花费\\n\");

printf(\"===================================\\n\"); printf(\" 请选择：1或2或3或4或5或6， 选择 0 退出： \"); scanf(\"%d\ if(xz ==2) { Floyd(G,n);//调用费洛伊德算法 printf(\"输入源点和终点：v，w： \"); scanf(\"%d,%d\ k=P[v][w];//k为起点v的后继顶点 if(k==0) printf(\" 顶点 %d到%d无路径！\\n\ else { printf(\" 从顶点%d到%d的最短路径是： %d\ while(k!=w) { printf(\"->%d\输出后继顶点 k=P[k][w];//继续找下一个顶点 } printf(\"->%d\输出终点w printf(\"路径长度：%d\\n\ } } else if(xz==1) { printf(\"求单源路径，输入源点v: \"); scanf(\"%d\ Dijkstra(G,v,n);//调用迪杰斯特拉算法 } else if(xz==0) exit(0); if(xz==3) { printf(\"求单源耗费时间，输入源点v: \"); scanf(\"%d\ Dijkstime(G,v,n); }

if(xz ==4) { Flotime(G,n);//调用费洛伊德算法

printf(\"输入源点和终点：v，w： \"); scanf(\"%d,%d\ k=P[v][w];//k为起点v的后继顶点 if(k==0) printf(\" 顶点 %d到%d无时间！\\n\ else { printf(\" 从顶点%d到%d的最短时间是： %d\ while(k!=w) { printf(\"->%d\输出后继顶点 k=P[k][w];//继续找下一个顶点 } printf(\"->%d\输出终点w printf(\"耗费时间：%d\\n\ } } if(xz==5) { printf(\"求单源花费多少，输入源点v: \"); scanf(\"%d\ Dijkscost(G,v,n); } if(xz ==6) { Flocost(G,n);//调用费洛伊德算法 printf(\"输入源点和终点：v，w： \"); scanf(\"%d,%d\ k=P[v][w];//k为起点v的后继顶点 if(k==0) printf(\" 顶点 %d到%d无花费！\\n\ else { printf(\" 从顶点%d到%d的最少花费是： %d\ while(k!=w) { printf(\"->%d\输出后继顶点 k=P[k][w];//继续找下一个顶点 } printf(\"->%d\输出终点w printf(\"花费多少：%d\\n\ } } }

printf(\"结束求最短路径，再见！\\n\"); }