《算法分析与实践》-作业2 Floyd算法和Dijkstra算法
程序员文章站
2024-03-16 13:16:58
...
Floyd算法和Dijkstra算法是研究最短路径问题的经典算法。本次实验将通过两道例题探究两种算法的操作过程并编写算法。
题目1
用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵(顶点之间的最短距离矩阵)
解析:
(1)首先初始化点与点之间的距离,用邻接矩阵存储。
1 | 2 | 3 | 4 | |
---|---|---|---|---|
1 | 0 | 2 | 6 | 4 |
2 | ∞ | 0 | 3 | ∞ |
3 | 7 | ∞ | 0 | 1 |
4 | 5 | ∞ | 12 | 0 |
(2)对第一行,也就是从1出发到各个点的距离做检查,看是否存在中间点v使得1->v->n存在更近的距离。
1 | 2 | 3 | 4 | |
---|---|---|---|---|
1 | 0 | 2 | 2+3=5 | 4 |
(3)对第二行重复(2)操作
1 | 2 | 3 | 4 | |
---|---|---|---|---|
2 | 3+1+5=9 | 0 | 3 | 3+1=4 |
(4)对第三行重复操作
1 | 2 | 3 | 4 | |
---|---|---|---|---|
3 | 1+5=6 | 1+5=6 | 0 | 1 |
(5)对第四行重复操作
1 | 2 | 3 | 4 | |
---|---|---|---|---|
4 | 5 | 5+2=7 | 5+2+3=10 | 0 |
这样,我们就得到了顶点之间的最短距离矩阵。
接下来,我们来看一下代码核心部分:
void Floyd(MGraph G){
int i,j,k;
for(i=1;i<=G.n;i++){
for(j=1;j<=G.n;j++){
dis[i][j]=G.weight[i][j];
}
}
for(k=1;k<=G.n;k++){ //1,2...G.n为经过的中间点
for(i=1;i<=G.n;i++){ //矩阵的行
for(j=1;j<=G.n;j++){ //矩阵的列
if(dis[i][j]>dis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j]; //若以k为中间点检测到更短的路径则更新最短路径
}
}
}
}
}
分析:
Floyd算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边,通过考虑最佳子路径来得到最佳路径。
- 单独一条边的路径也不一定是最佳路径。
- 从任意一条单边路径开始,我们可以知道所有两点之间的距离是边的权或无穷大;若两点之间没有边相连,对于每一对顶点a和b,看看是否存在一个中间顶点c使得从a到 c再到b比己知的ac路径更短。如果是那么更新距离。
- 有三重for循环,时间复杂度为O(n3)。
题目2
对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。
解析:
- 首先确定起点a(标为绿色);然后在从a出发、与a相连的点组成的边中找到权值最小的成为当前最短路径,并确定下一个起点b(标为红色)。
- b成新的起点(标为绿色);从b出发只能到d,所以b->d是最短路径,确定下一个起点为d(表为红色)。
- d成为新的起点(标为绿色);从d出发的有两条边,并且权值最小的是d->c。但是我们可以发现,如果到了c,那么再下一次就会回到a,违背了题目到达h的要求,所以不能选择c,应该选择权值第二小的d->f。所以f成为下一次的起点(标为红色)。
- f成为新的起点(标为绿色);从f出发的只有f->e,所以e成为下一次的起点(标为红色)。
- e成为新的起点(标为绿色);从e出发有两条边且权值相同,但是其中d点已经去过,所以我们选择去没有去过的g。g成为下一次的起点(标为红色)。
- g成为新的起点(标为绿色);从g出发有两条边且权值相同,但g->h可以直接抵达终点,所以选择g->h。
- 到达h(标为绿色)。所以a到h的最短路径为图中绿色的线路。
代码如下:
void Dijkstra(int n,int G[][MAX],int start,int end,int dis[],int path[]){
int min,v=0; //min用来存储最短距离,v用来临时存放当前最短路径经过的单个点
for(int i=0;i<n;i++){ //初始化
dis[i]=G[start][i]; //每个点距离起点的距离
vis[i]=0; //当前未访问
if(G[start][i]<INF) //如果当前点与起点连通,则标记为路径
path[i]=start;
else
path[i]=-1;
}
vis[start]=1; //起点标记为已经访问过
path[start]=-1; //起点不算做路径,主要用于输出判断
for(int i=0;i<n-1;i++){ //处理其余顶点
min=INF; //最短路径初始化
for(int j=0;j<n;j++){
if(vis[j]==0&&dis[j]<min){//如果j未访问过并且起点到j的路径小于当前最短路径
v=j; //标记j
min=dis[j]; //更新最短路径
}
}
vis[v]=1; //剩下点中有最短路径的点标记为已访问
for(int j=0;j<n;j++){ //更新距离和经过的点
if(vis[j]==0&&dis[v]+G[v][j]<dis[j]){
dis[j]=dis[v]+G[v][j];
path[j]=v;
}
}
if(v==end) //到终点后结束
return;
}
}
分析:
Dijkstra算法是一种贪心思想:
- 每次从子图中找到一条通往未知顶点的最短路径(D->E),将此路中的未知顶点E加入子图;
- 贪心思想的核心:把刚加入子图的顶点E当成中转点,考虑子图(C、D)经过中转点E到其他顶点的路会不会更近;
- 重复以上步骤,直到子图成为完整的图。
- 时间复杂度为O(n2)。
最后,附上源码地址:https://github.com/fanqyoo/GitDemo
欢迎批评指正~
上一篇: 最短路径-Floyd算法
下一篇: 最短路径 Floyd算法