数据结构应用实例(六)——最短路径

一、题目描述

  实现求最短路径的两种算法：Dijsktra 算法和 Floyd 算法；

二、算法思想

1. Dijkstra算法
   求一个点到图中其余节点的最短路径；
   首先设置三个辅助数组：
     (1)$flag，flag[i]==1$ 表示已求得起点到节点 $i$ 的最短路径；
     (2)$pre，pre[i]$ 表示节点 $i$ 的前驱；
     (3)$dis，dis[i]$ 表示已经求得最短路径中的点到点 $i$ 的最短路径长度；
   然后进行以下步骤：
   (1)、初始化(不妨设起点编号为0)：$flag[0]=1,flag[i]=0,i=1,2,\cdots ,n-1；$
   $dis[0]=0,dis[i]=G\to A[0][i],i=1,2,\cdots ,n-1；$
   $pre[0]=0,pre[i]=0$ 如果 $dis[i]<\infty ，pre[i]=-1$ 如果 $dis[i]==\infty ，i=1,2,\cdots ,n-1$；
   (2)、选择 d i s [ j ] = M i n { d i s [ i ] ∣ f l a g [ i ] = = 0 } dis[j]=Min\lbrace dis[i] | flag[i]==0 \rbrace dis[j]=Min{dis[i]∣flag[i]==0}，如果 $dis[j]<\infty$，使 $flag[j]=1$ ；
   (3)、更新 $dis[i]$ 和 $pre[i]$，$i$ 号节点为 $j$ 号节点的直接后继且 $flag[i]==0$，如果 $dis[i]>dis[j]+G\to A[j][i]$，令 $dis[i]=dis[j]+G\to A[j][i],pre[i]=j$，程序中使用邻接表进行处理；
   (4)、重复步骤(2)、(3)，直到 $flag[i]=1,i=0,1,\cdots ,n-1$ 或者选择的节点 $j$ 满足 $dis[j]==\infty$；
   经过上述过程即可求得起点到可到达节点的最短路径；

2. Floyd 算法
   求图中任意两点间的最短路径；
   以求顶点 $v_i$ 到 $v_j$ 的最短路径为例，$G\to A[i][j]$ 不一定恰好是最短路径，也许经过其他节点中转后得到的路径长度更短，因此需要进行 n 次试探；
     第 k 次试探，中间节点的编号均不超过 k-1，从第 k 次到第 k+1 次的做法，添加节点 k，如果 $v[1,\cdots ,k]$ 和 $v[k,\cdots ,j]$ (中间节点的编号均不超过 k-1) 拼接成的路径 $v[i,\cdots ,k,\cdots ,j]$比 $v[i,\cdots ,j]$ (中间节点的编号均不超过 k-1) 长度更短，则更新 $v_i$ 到 $v_j$ 的路径；经过 n 次试探之后，得到 $v[i,\cdots ,j]$ (中间节点的编号均不超过 n-1)，此时的路径即为 $v_i$ 到 $v_j$ 的最短路径；
     编程时采用两个辅助数组 $path$ 和 $D$，$path[i][j]$ 记录 $v_i$ 到 $v_j$ 的路径上的最后一个中转点，初始值为 $i$；$D[i][j]$ 记录 $v_i$ 到 $v_j$ 的路径长度，$D$ 初始值为 $G\to A$；进行 n 次试探，也就是对 $path$ 和 $D$ 进行了 n 次更新，最终得到想要结果；

三、代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxx 99999
#pragma warning(disable:4996)typedef struct arc//弧
{	int index;//指向节点编号int weight;//边的权值struct arc *next;
}AR;typedef struct MyGraph//图(包含邻接矩阵和邻接表)
{int type;//0表示无向图，1表示有向图int arcnum,vexnum;//边的个数、顶点个数char **vexname;//存放顶点名称的二维数组	AR *N;//表头数组int **A;//邻接矩阵
}GH;int findvex(char *s,GH *G);//找到图G中名称为s的节点编号，并将其返回
void createGraph(GH *G);//创建图G
void showGraph(GH *G);//以邻接表的形式显示图G
void Dijkstra(GH *G,char *start);//Dijkstra算法求图G中点start到其余节点的最短路径
void Floyd(GH *G);//Floyd算法求图G中任意两点间的最短路径
void showPath(GH *G,int **path,int i,int j);//递归输出Floyd算法中i号节点到j号节点的最短路径，path存放最后一个中转点int main(void)
{char start[20];GH *G=(GH *)malloc(sizeof(GH));//创建图createGraph(G);printf("图的邻接表形式:\n");showGraph(G);//Dijkstra算法printf("\n=========================Dijkstra算法===============================\n");printf("请输入起点名称(#表结束):\n");scanf("%s",start);while (strcmp(start, "#")){Dijkstra(G,start);printf("\n请输入起点名称(#表结束):\n");scanf("%s",start);}system("pause");printf("\n\n===========================Floyd算法===============================\n");//Floyd算法Floyd(G);printf("\n");free(G);return 0;
}int findvex(char *s,GH *G)//找到图G中名称为s的节点编号，并将其返回
{for(int i=0;i<G->vexnum;i++){if(strcmp(s,G->vexname[i])==0)//找到匹配节点return i;}printf("该点不存在\n");exit(-1);
}void createGraph(GH *G)//创建图G
{int i,j,n,edge;char filename[]="graph1.txt";//存放图的数据文件char str[10],str1[10];FILE *fp;AR *p;fp=fopen(filename,"r");if(!fp){printf("打开文件失败!\n");exit(-1);}fscanf(fp,"%d",&G->type);//读取图的类型G->arcnum=0;fscanf(fp,"%d",&n);//读取结点数量G->vexnum=n;//为动态数组分配空间G->vexname=(char **)malloc(n*sizeof(char *));G->N=(AR *)malloc(n*sizeof(AR));G->A=(int **)malloc(n*sizeof(int *));//对头结点数组和邻接矩阵初始化for (i = 0; i < n; i++){G->N[i].next = NULL;G->A[i] = (int *)malloc(n*sizeof(int));for (j = 0; j < n; j++)G->A[i][j]=maxx;}//读取顶点名称for(i=0;i<n;i++){fscanf(fp,"%s",str);G->vexname[i]=(char *)malloc(strlen(str)*sizeof(char));strcpy(G->vexname[i],str);}//读取边while(!feof(fp)){fscanf(fp,"%s",str);fscanf(fp,"%s",str1);fscanf(fp,"%d",&edge);i=findvex(str,G);j=findvex(str1,G);//邻接表p=(AR *)malloc(sizeof(AR));p->index=j;p->weight=edge;p->next=G->N[i].next;G->N[i].next=p;//邻接矩阵G->A[i][j]=edge;G->arcnum++;//边的个数增加if(G->type==0)//如果是无向图{//邻接表p=(AR *)malloc(sizeof(AR));p->index=i;p->weight=edge;p->next=G->N[j].next;G->N[j].next=p;//邻接矩阵G->A[j][i]=edge;}}fclose(fp);
}void showGraph(GH *G)//以邻接表的形式显示图G
{int i;AR *p;//用于遍历for (i = 0; i < G->vexnum; i++){printf("%s",G->vexname[i]);p=G->N[i].next;while (p){if (G->type == 1)printf("-->");else//无向图没有箭头printf("--");printf("%s(%d)",G->vexname[p->index],p->weight);p=p->next;}printf("\n");}printf("\n");
}void Dijkstra(GH *G,char *start)//Dijkstra算法求图G中点start到其余节点的最短路径
{int i,n,begin,next;int min;int *flag,*dis,*pre;int *t,top,p;AR *q;begin=findvex(start,G);//起点编号n=G->vexnum;flag=(int *)malloc(n*sizeof(int));//指示是否找到最短路径dis=(int *)malloc(n*sizeof(int));//已求得最短路径的点到该点的最短路径的长度pre=(int *)malloc(n*sizeof(int));//前驱t=(int *)malloc(n*sizeof(int));//建立栈，存储路径//数组初始化for (i = 0; i < n; i++){flag[i]=0;dis[i]=G->A[begin][i];if (dis[i] < maxx)pre[i]=begin;elsepre[i]=-1;}flag[begin]=1;dis[begin]=0;pre[begin]=-1;//在未找到最短路径的点中挑选路径最短的点min=maxx;for (i = 0; i < n; i++){if (flag[i] == 0 && dis[i] < min){min=dis[i];next=i;}}while(min < maxx)//找到之后，如果min<maxx，说明有新的点的flag将会被设为1{flag[next]=1;q=G->N[next].next;while (q)//更新next的未找到最短路径的直接后继的最短路径长度和前驱{if (flag[q->index] == 0 && dis[q->index] > dis[next] + (q->weight)){dis[q->index]= dis[next] + (q->weight);pre[q->index]=next;}q=q->next;}		//继续寻找最近点min=maxx;for (i = 0; i < n; i++){if (flag[i] == 0 && dis[i] < min){min=dis[i];next=i;}}}//寻找结束，结果输出printf("\n起点到各个顶点的最短路径:\n\n");for (i = 0; i < n; i++){if(i==begin)continue;printf("%s--%s:",G->vexname[begin],G->vexname[i]);if (pre[i] == -1)printf("从起点出发无法到达该点\n");else{top = -1;p = i;  while (p != begin)//将前驱依次放入栈中{top++;t[top] = p;p = pre[p];}printf("%s",G->vexname[begin]);while (top >= 0)//利用栈实现路径的正向输出{p=t[top];top--;printf("-->%s",G->vexname[p]);}printf("  最短路径长度为:%d\n",dis[i]);}printf("\n");}free(flag);free(dis);free(pre);free(t);
}void Floyd(GH *G)//Floyd算法求图G中任意两点间的最短路径
{int i,j,k,n;int **path,**D;n=G->vexnum;//节点个数path=(int **)malloc(n*sizeof(int*));//两点间最短路径上的最后一个中转点D=(int **)malloc(n*sizeof(int*));//两点间最短路径长度//初始化for (i = 0; i < n; i++){path[i]=(int *)malloc(n*sizeof(int));D[i]=(int *)malloc(n*sizeof(int));for (j = 0; j < n; j++){path[i][j]=i;D[i][j]=G->A[i][j];}}for (k = 0; k < n; k++)//中转点层为最外层for (i = 0; i < n; i++)for (j = 0; j < n; j++)if (D[i][j] > D[i][k] + D[k][j])//更新路径长度和中转点{D[i][j]= D[i][k] + D[k][j];path[i][j]=k;}//显示路径printf("\n两点间的最短路径为:\n");for (i = 0; i < n; i++){for (j = 0; j < n; j++){if(j==i)continue;printf("\n%s--%s:",G->vexname[i],G->vexname[j]);if (D[i][j] == maxx)printf("这两点之间没有路径\n");else{printf("%s",G->vexname[i]);showPath(G, path, i, j);printf("%s",G->vexname[j]);printf("  最短路径长度为:%d\n", D[i][j]);}}}free(path);free(D);
}void showPath(GH *G,int **path,int i,int j)//递归输出Floyd算法中i号节点到j号节点的最短路径，path存放最后一个中转点
{   //假定两点之间存在路径int k=path[i][j];//基准情况：没有中转点if(k==i)printf("-->");else//非基准情况{showPath(G,path,i,k);printf("%s",G->vexname[k]);showPath(G,path,k,j);}
}

四、小结

1、 采用递归的方式输出路径，为得到正确结果，将起点和终点放在递归函数外进行输出；
2、 迪杰斯特拉算法中，选择新加入的节点 $j$ 时，如果 $dis[j]==\infty$，算法也会结束；