求最短路径的两种算法（C语言实现）
http://dl.iteye.com/upload/attachment/496566/9dbdcd3c-6cd7-36c5-b19d-c9474c308bc7.jpg求这个有向网中任意两点的最短路径
/* * 最短路径，迪杰斯特拉算法和弗洛伊德算法（采用邻接矩阵存储） * */#include<stdio.h>#define MAX_VERTEX_NUM 20#define INFINITE 10000//当做无穷大//图的定义typedef struct {int vertexNum;char vertex;int arc;}Graph,*PGraph;//辅助数组中的元素定义typedef struct{int distance;int path;}ArrayNode;//构造有向网void createdGraph(PGraph g){int i,j; g->vertexNum=6; for(i=0;i<g->vertexNum;i++)g->vertex='A'+i;for(i=0;i<g->vertexNum;i++)for(j=0;j<g->vertexNum;j++) g->arc=0;g->arc=10;g->arc=30;g->arc=100;g->arc=5;g->arc=50;g->arc=10;g->arc=20;g->arc=60;}//迪杰斯特拉算法void Dijkstra(PGraph g,int from,int to){int i,j,index=-1;int n=1;//记录已经求出的两个点之间的最短距离的个数 ArrayNode shortestPath;int flag={0};//标记，为1表示到这个顶点的最短距离已求出//1.求from到各个顶点的直接距离，即初始化shortestPath数组for(i=0;i<g->vertexNum;i++){if(from==i){shortestPath.distance=0;shortestPath.path=i;flag=1;}else if(g->arc>0){ shortestPath.path=from; shortestPath.path=i;shortestPath.distance=g->arc;}else shortestPath.distance=INFINITE;}//2.每次求一个最短路径while(n<g->vertexNum){//选择shortestPath中距离最小的，求出from到这个顶点的最短路径index=-1;for(i=0;i<g->vertexNum;i++){if(i==from)continue;if(flag==0 && index==-1 && shortestPath.distance!=INFINITE)index=i;if(flag==0 && index!=-1 && shortestPath.distance<shortestPath.distance)index=i;}flag=1;//修改到各个顶点的最短路径for(i=0;i<g->vertexNum;i++){if(i==from)continue;if(g->arc>0 && g->arc+shortestPath.distance<shortestPath.distance){shortestPath.distance=g->arc+shortestPath.distance;//修改路径j=0; while(1){shortestPath.path=shortestPath.path;if(shortestPath.path==index)break;j++;} shortestPath.path=i;}}n++;}//输出from到to的最短路径及长度if(shortestPath.distance==INFINITE){printf("%c到%c没有路径\n",from+'A',to+'A');return;}printf("%c到%c的最短路径长度是：%d\n",from+'A',to+'A',shortestPath.distance);printf("经过的顶点：");i=0;while(1){printf("%-3c",shortestPath.path+'A'); if(shortestPath.path==to)break;i++;}printf("\n");}//弗洛伊德算法void Floyd(PGraph g,int from,int to){int i,j,k; int shortestPath;//存储最短路径的数组//初始化shortestPathfor(i=0;i<g->vertexNum;i++)for(j=0;j<g->vertexNum;j++){if(i==j){shortestPath=0;continue;}if(g->arc>0) shortestPath=g->arc;else shortestPath=INFINITE;}//将各个顶点顺次加入，并修改最短路径for(k=0;k<g->vertexNum;k++){//在i，j之间加入kfor(i=0;i<g->vertexNum;i++){for(j=0;j<g->vertexNum;j++){ if(shortestPath+shortestPath<shortestPath)shortestPath=shortestPath+shortestPath;}}}//输出最短路径if(shortestPath==INFINITE){printf("%c到%c没有路径\n",from+'A',to+'A');return;}printf("%c到%c的最短路径长度是：%d\n",from+'A',to+'A',shortestPath);printf("\n");}void main(){Graph graph;char from,to;createdGraph(&graph);printf("请输入起点终点(如AF，中间不要有空格)\n");scanf("%c%c",&from,&to);printf("\n迪杰斯特拉算法:\n"); Dijkstra(&graph,from-'A',to-'A');printf("\n弗洛伊德算法:\n");Floyd(&graph,from-'A',to-'A');}
页:
[1]