欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《算法分析与实践》-作业2 Floyd算法和Dijkstra算法

程序员文章站 2024-03-16 13:16:58
...

Floyd算法和Dijkstra算法是研究最短路径问题的经典算法。本次实验将通过两道例题探究两种算法的操作过程并编写算法。

题目1

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵(顶点之间的最短距离矩阵)《算法分析与实践》-作业2 Floyd算法和Dijkstra算法

解析:

(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的最短路径。
《算法分析与实践》-作业2 Floyd算法和Dijkstra算法

解析:
  1. 首先确定起点a(标为绿色);然后在从a出发、与a相连的点组成的边中找到权值最小的成为当前最短路径,并确定下一个起点b(标为红色)。
  2. b成新的起点(标为绿色);从b出发只能到d,所以b->d是最短路径,确定下一个起点为d(表为红色)。
  3. d成为新的起点(标为绿色);从d出发的有两条边,并且权值最小的是d->c。但是我们可以发现,如果到了c,那么再下一次就会回到a,违背了题目到达h的要求,所以不能选择c,应该选择权值第二小的d->f。所以f成为下一次的起点(标为红色)。
  4. f成为新的起点(标为绿色);从f出发的只有f->e,所以e成为下一次的起点(标为红色)。
  5. e成为新的起点(标为绿色);从e出发有两条边且权值相同,但是其中d点已经去过,所以我们选择去没有去过的g。g成为下一次的起点(标为红色)。
  6. g成为新的起点(标为绿色);从g出发有两条边且权值相同,但g->h可以直接抵达终点,所以选择g->h。
  7. 到达h(标为绿色)。所以a到h的最短路径为图中绿色的线路。
    《算法分析与实践》-作业2 Floyd算法和Dijkstra算法
    代码如下:
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
欢迎批评指正~