算法入门之单源最短路径算法:Dijkstra(迪杰斯特拉)算法

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

上节我们介绍了最短路径算法中经典的多源最短路径算法,就是求图中任意两点之间的最短路径,今天我们再介绍最短路径中另一个经典的算法,叫单源最短路径算法,顾名思义,就是求图中某一个顶点到其他顶点的最短路径,主要思想是以起始点为中心,向外层层扩展,直到扩展到所有的顶点。


首先看下面场景分析


算法入门之单源最短路径算法:Dijkstra(迪杰斯特拉)算法

假设现在我们就要求1号顶点到其他顶点的最短路径?


思路分析

  • 第一步:将所有的顶点我们划分为2类,一类是已经确定距离1号点最短路径的顶点集合A,另一类是未确定距离1号点最短路径的顶点集合B,我们用book[]来标记已确定最短路径的顶点,再以一个数组dis来保存每个点到1号点的当前最短距离,初始化时,我们A中只有一个顶点那就是1号点自己本身,并且book中打上标记book[1]=1;B中有除了1号点的23456号顶点;

  • 第二步:设置1号点到自己的距离为0即dis[1]=0,再存在1号点能直接到达的点,则设置dis[i]=e[1][i],即1到其他点的直达距离就为当前最短距离,不能直达的设置为dis[i]=∞;

  • 第三步:在未确定最短路径的集合B中选一个离1号点最近的点k放入A,并且判断从1出发经过k到其他点的路径是否小于当前1-k的距离,如果存在小于的点m则替换掉1-m的最短距离为1-k-m的距离,级dis[m]=dis[k]+e[k][m],我们称这一步为边的松弛;

  • 第四步:重复第三步,直到所有的点都放入A,则结束,最终dis中的值就是1到所有点的最短路径,我们把1号顶点称为源点,也就是单源顶点到其他点的最短路径;

ok?思路已经出来了,那我们就动手实现下吧,实现之前先看下下面这个二维数组e[][],1-6个顶点,9条边分别代表点-点之间路径

算法入门之单源最短路径算法:Dijkstra(迪杰斯特拉)算法

代码实现(Dijkstra算法实现单源最短路径)

public class Dijkstra {
   
// 单源最短路径
   
public static void main(String[] args) {
       
// 存顶点到每个点的距离数据
       
int[][] e = new int[10][10];
       
// 存储1号顶点其他点的初始距离
       
int[] dis = new int[7];
       
// 记录哪些点已知最短路径
       
int[] book = new int[7];
       int
max = 99999999;//代表无穷大
       
int n = 6; // 顶点数
       
int m = 9; //边数
       
int min; //最小值

       // 初始化二维数组e
       
for (int i = 1; i <= n; i++) {
           
for (int j = 1; j <= n; j++) {
               
if (i == j) {
                   e[i][j]
= 0;
               
} else {
                   e[i][j]
= max;
               
}
           }
       }
       
// 初始化边数据(m条有向边)
       
e[1][2] = 1;
       
e[1][3] = 12;
       
e[2][3] = 9;
       
e[2][4] = 3;
       
e[3][5] = 5;
       
e[4][3] = 4;
       
e[4][5] = 13;
       
e[4][6] = 15;
       
e[5][6] = 4;
       
// 初始化dis 初始化book
       
for (int i = 1; i <= n; i++) {
           dis[i]
= e[1][i];
           
book[i] = 0;
       
}
       
// 将顶点先标记为已经在已知最短路径集合中
       
book[1] = 1;
       
//
       
int tempj = 0;
       
// 核心算法部分
       
for (int i = 1; i <= n - 1; i++) {
           min
= max;
       
// 找到离1号顶点最近的顶点,
        // 每次循环结束都能确定一个离1号点最近的点
           
for (int j = 1; j <= n; j++) {
       
//当前点还未确定最小路径,且当前点到1点的距离小于
        //最小值更新最小值min,遍历直到n个顶点都遍历完,
        // 最终得到离1号点最小的那个值
               
if (book[j] == 0 && dis[j] < min) {
                   min
= dis[j];
                   
tempj = j;
               
}
           }
     
// 标记找到的顶点j为已确定最小路径的点
           
book[tempj] = 1;
     
// 已tempj顶点为起点(此时tempj离1点最小路径已确定),
           // 对每个点进行一次比较
           
for (int v = 1; v <= n; v++) {
 
// 当tempj到v顶点的距离小于无穷大并且1号点到tempj顶点的距离
  //加上tempj点到v点的距离小于,1号点到v点的距离时
  // 说明已经找到一条比1-v更短的路径1-tempj-v,更新最小值dis[v]
   
if (e[tempj][v] < max && dis[v] > dis[tempj] + e[tempj][v]) {
            dis[v]
= dis[tempj] + e[tempj][v];
         
}
      }
   }
 
for (int i = 1; i <= n; i++) {
 
System.out.println("1号点到"+i+"号顶点的最短路径为:"+dis[i]+"");
 
}
}
}
结果:
   1号点到1号顶点的最短路径为:0
   1号点到2号顶点的最短路径为:1
   1号点到3号顶点的最短路径为:8
   1号点到4号顶点的最短路径为:4
   1号点到5号顶点的最短路径为:13
   1号点到6号顶点的最短路径为:17


源点1到各顶点之间的最短距离最终得出来了;

算法入门之单源最短路径算法:Dijkstra(迪杰斯特拉)算法

                                       

算法入门之单源最短路径算法:Dijkstra(迪杰斯特拉)算法

总结

  • Dijkstra算法时间复杂度为O(N(N+M)),忽略常数,所以为O(N²),每次寻找离源点最近点的时间复杂度为O(N);

  • 因为Dijkstra基于边计算的,所以对于边比较多的图(稠密图)我们其实可以采用邻接表代替矩阵来存储,从来减小时间复杂度(有兴趣的可以自己去查阅相关资料);

  • Dijkstra算法是一种基于贪心策略的算法,每次扩展到一个新的最短路径点,就更新他相邻的点的路径,因为每个边都是正值,所以这个新的点到源点的最短路径就确定了,不会发生改变,当所有顶点都被扩展到,就完成整个算法;

  • 上一点提到了每个边都是正值,所以Dijkstra算法不允许用在有负权的边上,因为有负值的话,每次扩展到该点他的最短路径都在减小,永远不能确定最小路径,也就无法继续后续顶点的扩展;


相关文章:

算法入门之多源路径算法:Floyd(弗洛伊德)算法








原文始发于微信公众号(Justin的后端书架):算法入门之单源最短路径算法:Dijkstra(迪杰斯特拉)算法