数据结构应用实例(六)——最短路径
Content:
- 一、题目描述
- 二、算法思想
- 三、代码实现
- 四、小结
一、题目描述
实现求最短路径的两种算法:Dijsktra 算法和 Floyd 算法;
二、算法思想
-
Dijkstra算法
求一个点到图中其余节点的最短路径;
首先设置三个辅助数组:
(1) f l a g , f l a g [ i ] = = 1 flag,flag[i]==1 flag,flag[i]==1 表示已求得起点到节点 i i i 的最短路径;
(2) p r e , p r e [ i ] pre,pre[i] pre,pre[i] 表示节点 i i i 的前驱;
(3) d i s , d i s [ i ] dis,dis[i] dis,dis[i] 表示已经求得最短路径中的点到点 i i i 的最短路径长度;
然后进行以下步骤:
(1)、初始化(不妨设起点编号为0): f l a g [ 0 ] = 1 , f l a g [ i ] = 0 , i = 1 , 2 , ⋯ , n − 1 ; flag[0]=1, flag[i]=0, i=1,2,\cdots,n-1; flag[0]=1,flag[i]=0,i=1,2,⋯,n−1;
d i s [ 0 ] = 0 , d i s [ i ] = G → A [ 0 ] [ i ] , i = 1 , 2 , ⋯ , n − 1 ; dis[0]=0, dis[i]=G\to A[0][i], i=1,2,\cdots,n-1; dis[0]=0,dis[i]=G→A[0][i],i=1,2,⋯,n−1;
p r e [ 0 ] = 0 , p r e [ i ] = 0 pre[0]=0, pre[i]=0 pre[0]=0,pre[i]=0 如果 d i s [ i ] < ∞ , p r e [ i ] = − 1 dis[i]<\infty,pre[i]=-1 dis[i]<∞,pre[i]=−1 如果 d i s [ i ] = = ∞ , i = 1 , 2 , ⋯ , n − 1 dis[i]==\infty,i=1,2,\cdots,n-1 dis[i]==∞,i=1,2,⋯,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},如果 d i s [ j ] < ∞ dis[j]<\infty dis[j]<∞,使 f l a g [ j ] = 1 flag[j]=1 flag[j]=1 ;
(3)、更新 d i s [ i ] dis[i] dis[i] 和 p r e [ i ] pre[i] pre[i], i i i 号节点为 j j j 号节点的直接后继且 f l a g [ i ] = = 0 flag[i]==0 flag[i]==0,如果 d i s [ i ] > d i s [ j ] + G → A [ j ] [ i ] dis[i]>dis[j]+G\to A[j][i] dis[i]>dis[j]+G→A[j][i],令 d i s [ i ] = d i s [ j ] + G → A [ j ] [ i ] , p r e [ i ] = j dis[i]=dis[j]+G\to A[j][i], pre[i]=j dis[i]=dis[j]+G→A[j][i],pre[i]=j,程序中使用邻接表进行处理;
(4)、重复步骤(2)、(3),直到 f l a g [ i ] = 1 , i = 0 , 1 , ⋯ , n − 1 flag[i]=1,i=0,1,\cdots,n-1 flag[i]=1,i=0,1,⋯,n−1 或者选择的节点 j j j 满足 d i s [ j ] = = ∞ dis[j]==\infty dis[j]==∞;
经过上述过程即可求得起点到可到达节点的最短路径; -
Floyd 算法
求图中任意两点间的最短路径;
以求顶点 v i v_i vi 到 v j v_j vj 的最短路径为例, G → A [ i ] [ j ] G\to A[i][j] G→A[i][j] 不一定恰好是最短路径,也许经过其他节点中转后得到的路径长度更短,因此需要进行 n 次试探;
第 k 次试探,中间节点的编号均不超过 k-1,从第 k 次到第 k+1 次的做法,添加节点 k,如果 v [ 1 , ⋯ , k ] v[1,\cdots,k] v[1,⋯,k] 和 v [ k , ⋯ , j ] v[k,\cdots,j] v[k,⋯,j] (中间节点的编号均不超过 k-1) 拼接成的路径 v [ i , ⋯ , k , ⋯ , j ] v[i,\cdots,k,\cdots,j] v[i,⋯,k,⋯,j]比 v [ i , ⋯ , j ] v[i,\cdots,j] v[i,⋯,j] (中间节点的编号均不超过 k-1) 长度更短,则更新 v i v_i vi 到 v j v_j vj 的路径;经过 n 次试探之后,得到 v [ i , ⋯ , j ] v[i,\cdots,j] v[i,⋯,j] (中间节点的编号均不超过 n-1),此时的路径即为 v i v_i vi 到 v j v_j vj 的最短路径;
编程时采用两个辅助数组 p a t h path path 和 D D D, p a t h [ i ] [ j ] path[i][j] path[i][j] 记录 v i v_i vi 到 v j v_j vj 的路径上的最后一个中转点,初始值为 i i i; D [ i ] [ j ] D[i][j] D[i][j] 记录 v i v_i vi 到 v j v_j vj 的路径长度, D D D 初始值为 G → A G\to A G→A;进行 n 次试探,也就是对 p a t h path path 和 D D 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;
else
pre[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
j
j 时,如果
d
i
s
[
j
]
=
=
∞
dis[j]==\infty
dis[j]==∞,算法也会结束;