最短路径——Dijkstra算法与Floyd算法

简介: 最短路径——Dijkstra算法与Floyd算法

最短路径问题

最短路径问题是我们经常会面临的一种决策问题。在图论中,非网图(边没有权值)的最短路径就是两个顶点之间经过边数最少的路径。对于网来说,由于每条边都有权值,所谓的最短路径是指,两个顶点之间经过的边加权之后的和最小。路径上的第一个顶点称为源点,最后一个顶点称为终点。求最短路径的经典算法有Dijkstra算法和Floyd算法。


Dijkstra算法

Dijkstra算法主要解决从某个源点到其余各个顶点的最短路径问题,它是一种按路径长度递增的次序来产生最短路径的算法。下面介绍算法思想。

首先给出一个6顶点的图,求v0到v5之间的最短路径

第一步,从v0开始到下一个顶点的权值最小边所对应的终点,从v0出发有两条边,v0v1和v0v2,权值更小的是v0v1;

第二步,v1到下一个顶点的最小权值边,从三个待选项中选出权值最小的边;

一直这样寻找下去,直到到达终点v5。

C语言代码实现

/* Dijkstra算法 */
#define MAXVEX 6
#define INFINITY 65535
typedef struct _graph_type
{
  int vertex[MAXVEX]; /*顶点*/
  int arc[MAXVEX][MAXVEX]; /*邻接矩阵*/
  int vertex_num;
}graph_type;
typedef int pv_type[MAXVEX];    /* 用于存储最短路径下标的数组 */
typedef int plen_type[MAXVEX];  /* 用于存储到各点最短路径的权值和 */
/*
 * graph    : 图
 * v0     :起始顶点
 * path_vector  :记录路径中vi顶点的上一个顶点的数组,[0, 0, 1]表示v2上一个顶点是v1,v1上一个顶点是v0
 *          数组下标表示i,相应的值表示上一个顶点的下标 --- 实际上就是记录路径的
 * path_length  :v0到vi之间的路径和的数组
*/ 
void ShortestPath_Dijkstra(graph_type graph, int v0, pv_type *path_vector, plen_type *path_length)
{    
  int v;
  int w;
  int k; /*记录最小权值的边的顶点*/
  int min; /*记录最小权值*/    
  int flag[MAXVEX];/* 标志是否找到最小路径,flag[w]=1表示求得顶点v0至vw的最短路径 */
  for(v=0; v<graph.vertex_num; v++)    /* 初始化数据 */
  {        
    flag[v] = 0; /* 全部顶点初始化为未知最短路径状态 */
    (*path_length)[v] = graph.arc[v0][v]; /* 根据邻接矩阵将与v0点有连线的顶点加上权值 */
    (*path_vector)[v] = -1; /* 初始化路径数组P为-1  */       
  }
  (*path_length)[v0] = 0;  /* v0至v0路径为0 */  
  flag[v0] = 1;    /* v0至v0不需要求路径 */  
  /* 开始主循环,每次求得v0到某个v顶点的最短路径 */   
  for(v=1; v<graph.vertex_num; v++)   
  {
    min=INFINITY;    /* min初始化为无穷大 */        
    for(w=0; w<graph.vertex_num; w++) /* 寻找离v0最近的顶点 */    
    {            
      if(!flag[w] && (*path_length)[w]<min) /* 遍历path_length数组,找到最小权值 */            
      {                   
        k=w; /* 记录最小权值顶点 */                     
        min = (*path_length)[w];    /* 更新min,w顶点离v0顶点更近 */            
      }        
    }        
    flag[k] = 1;    /* 已找到,标志置1 */
    for(w=0; w<graph.vertex_num; w++) /* 修正当前最短路径及距离 */
    {
      /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
      if(!flag[w] && (min+graph.arc[k][w]<(*path_length)[w]))   
      { /*  说明找到了更短的路径,修改path_length[w]和path_vector[w] */
        (*path_length)[w] = min + graph.arc[k][w];  /* 修改当前路径长度 */               
        (*path_vector)[w]=k; /*记录上一个顶点*/        
      }       
    }   
  }
}

代码解析

本代码略显复杂,有些晦涩难懂,下面讲解本代码的思路:

首先看代码中的注释,了解每个变量的用途,这里要关注三个数组path_vector、path_length和flag。在主循环之前都是声明和初始化的工作,下面从主循环开始讲解。

主循环第一次循环: 首先,主循环的作用是通过每一次循环得到源点v0到一个顶点的最短路径,v从1开始循环。

path_length数组用于保存路径和,第一次循环的时候为[0, 1, 4, 65535, 65535, 65535],第一个0表示v0和v0之间不需要计算路径,1表示v0到v1之间的权值为1,4表示v0到v3之间权值为4,后面的65535表示没有路径。

然后遍历path_length数组,找到最小的权值,记录下该权值以及对应的终点

现在,v0到v1之间的路径找到了,那么更新flag为[1, 1, 0, 0, 0, 0],前两个1表示v0v0之间不需要找,v0v1之间的最短路径已找到。后面每找到v0到某一顶点的最短路径,就把flag数组中对应下标的数组元素值改为1。

修正最短路径: 这是最重要的一步,主要是为了修正path_length数组中的值。首先,经过前面的操作之后,该数组值当前是[0, 1, 4, 65535, 65535, 65535],也就是说v0到v1最短路径为1,这个毫无疑义,但是v0到v2最短路径是4,这个4是从邻接矩阵中直接拿过来的,并没有经过任何算法的检验,所以我们要修正这个值。

我们看图,从v0到v2目前有两条路,第一条v0v2,权值为4;第二条v0v1v2,权值为3。显然后者权值更小,我们应对数组path_length中的4进行修正。

在修正最短路径的同时,我们应该把这条路径记录下来,也就是说v0是怎么到达v2的,是v0v2还是v0v1v2,这个路径是通过path_vector来记录的。

OK,第一轮循环结束,后面就是不断地重复这个过程,直到找出最短路径。在最后一次循环,我们得到的path_length和path_vector应该分别是:

path_length = [0, 1, 3, 6, 10, 15]
path_vector = [-1, 0, 1, 2, 3, 4]

[0, 1, 3, 6, 10, 15]表示,v0-v1之间最短路径是1,v0-v2之间最短路径是3,v0-v3之间最短路径是6,v0-v4最短路径是10,v0-v5最短路径是15。

[-1, 0, 1, 2, 3, 4]表示,v1的上一个顶点是0,v2的上一个顶点是v1,v3的上一个顶点是v2,v4的上一个顶点是v3,v5的上一个顶点是v4,这样就形成了一条路径v5 --> v4 --> v3 --> v2 --> v1 --> v0。

通过这两个数组我们可以看出,Dijkstra算法只能得到某一个顶点到其它任意顶点的最短路径,比如v0分别到v12345之间的最短路径,但是无法得到诸如v2到v4之间的最短路径,这就要看Floyd算法了。

Floyd算法

算法解析

依然是使用上面的图

算法开始,首先初始化两个矩阵,path_length用于记录最短路径的长度,初始值为图的邻接矩阵;path_vector用来记录路径,也就是中转结点,可以结合程序来理解。

我们来看所有以v1为中转点的路径,也就是path_length矩阵的v1列,path_length,首先看图,经过v1中转可以到达v2、v3、v4,我们分别计算出v0 --> v1 --> v2,v0 --> v1 --> v3,v0 --> v1 --> v4的路径长度为3,7,4,然后分别和path_length矩阵中记录的v0 --> v2,v0 --> v3,v0 --> v4的最短路径值做对比,并更新path_length矩阵。

相应的,我们要修改路径矩阵中对应的位置,此时应该记录下来v2、v3、v4三个顶点的前驱顶点,它们分别是由v1顶点中转,此时将path_vector中v0 --> v2,v0 --> v3,v0 --> v4的中转结点记录为v1,表示在矩阵中就是path_vector[0][2]、path_vector[0][3]、path_vector[0][4]的值设置为1。

下面就是从以v2为中转点的路径开始重复上述过程,直到算法计算完以v4为中转顶点的路径,得到最终的path_length和path_vector矩阵。

C语言代码实现

/*Floyd算法*/
#define MAXVEX 6
#define INFINITY 65535
typedef struct _graph_type
{
  int vertex[MAXVEX];
  int arc[MAXVEX][MAXVEX];
  int vertex_num;
}graph_type;
/*在Dijkstra算法中这两个都是一维数组,但是Floyd算法求的是任意顶点到其他顶点的最短路径,所以是二维数组*/
typedef int pv_type[MAXVEX][MAXVEX];
typedef int plen_type[MAXVEX][MAXVEX];
/* 求网图graph中各顶点v到其余顶点w的最短路径path_vector[v][w]及带权长度path_length[v][w]。 */    
void ShortestPath_Floyd(graph_type graph, pv_type *path_vector, plen_type *path_length)
{    
  int v; /*起点*/
  int w; /*终点*/
  int k; /*中转点*/   
  for(v=0; v<graph.vertex_num; ++v) /* 初始化 */  
  {        
    for(w=0; w<graph.vertex_num; ++w)  
    {
      (*path_length)[v][w]=graph.arc[v][w]; /* path_length初始化为邻接矩阵 */
      (*path_vector)[v][w]=w;       /* 初始化path_vector */
    }
  }
  for(k=0; k<graph.vertex_num; ++k)   
  {
    for(v=0; v<graph.vertex_num; ++v)  
    {        
      for(w=0; w<graph.vertex_num; ++w)    
      {
        if ((*path_length)[v][w]>(*path_length)[v][k]+(*path_length)[k][w])
        {/* 如果经过下标为k顶点路径比原两点间路径更短 */
          (*path_length)[v][w]=(*path_length)[v][k]+(*path_length)[k][w];/* 将当前两点间权值设为更小的一个 */
          (*path_vector)[v][w]=(*path_vector)[v][k];/* 路径设置为经过下标为k的顶点 */
        }
      }
    }
  }
}


目录
打赏
0
0
0
0
13
分享
相关文章
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
126 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
151 68
基于包围盒的机械臂防碰撞算法matlab仿真
基于包围盒的机械臂防碰撞算法通过构建包围盒来近似表示机械臂及其环境中各实体的空间占用,检测包围盒是否相交以预判并规避潜在碰撞风险。该算法适用于复杂结构对象,通过细分目标对象并逐级检测,确保操作安全。系统采用MATLAB2022a开发,仿真结果显示其有效性。此技术广泛应用于机器人运动规划与控制领域,确保机器人在复杂环境中的安全作业。
基于WOA鲸鱼优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB 2022a实现时间序列预测,采用CNN-GRU-SAM网络结构,结合鲸鱼优化算法(WOA)优化网络参数。核心代码含操作视频,运行效果无水印。算法通过卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征,全连接层整合输出。数据预处理后,使用WOA迭代优化,最终输出最优预测结果。
基于SOA海鸥优化算法的三维曲面最高点搜索matlab仿真
本程序基于海鸥优化算法(SOA)进行三维曲面最高点搜索的MATLAB仿真,输出收敛曲线和搜索结果。使用MATLAB2022A版本运行,核心代码实现种群初始化、适应度计算、交叉变异等操作。SOA模拟海鸥觅食行为,通过搜索飞行、跟随飞行和掠食飞行三种策略高效探索解空间,找到全局最优解。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等