数据结构与算法—单源最短路径dijkstra算法

简介: 对于dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法,但是可能不清楚其中的作用和原理,又或许,你曾经感觉它很难,那么,这个时候正适合你重新认识它。

介绍



对于dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法,但是可能不清楚其中的作用和原理,又或许,你曾经感觉它很难,那么,这个时候正适合你重新认识它。


Dijkstra能是干啥的?


20190909002921297.png


Dijkstra是用来求单源最短路径

就拿上图来说,假如直到的路径和长度已知,那么可以使用dijkstra算法计算南京到图中所有节点的最短距离。


单源什么意思?


  • 从一个顶点出发,Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。

bfs求的最短路径有什么区别?

  • bfs求的与其说是路径,不如说是次数。因为bfs他是按照队列一次一次进行加入相邻的点,而两点之间没有权值或者权值相等(代价相同)。处理的更多是偏向迷宫类的这种都是只能走邻居(不排除特例)。


Dijkstra在处理具体实例的应用还是很多的,因为具体的问题其实带权更多一些。


比如一个城市有多个乡镇,乡镇可能有道路,也可能没有,整个乡镇联通,如果想计算每个乡镇到a镇的最短路径,那么Dijkstra就派上了用场。


算法分析



对于一个算法,首先要理解它的运行流程

对于一个Dijkstra算法而言,前提是它的前提条件和环境:

  • 一个连通图,若干节点,节点可能有数值,但是路径一定有权值。并且路径不能为负。否则Dijkstra就不适用。


Dijkstra的核心思想是贪心算法的思想。不懂贪心?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。


对于贪心算法,在很多情况都能用到。下面举几个不恰当的例子!

打个比方,吃自助餐,目标是吃回本,那么胃有限那么每次都仅最贵的吃。

上学时,麻麻说只能带5个苹果,你想带最多,那么选五个苹果你每次都选最大的那个五次下来你就选的最重的那个。


不难发现上面的策略虽然没有很强的理论数学依据,或者不太好说明。但是事实规律就是那样,并且对于贪心问题大部分都需要排序,还可能会遇到类排序。并且一个物体可能有多个属性,不同问题需要按照不同属性进行排序,操作。


那么我们的Dijkstra是如何贪心的呢?对于一个点,求图中所有点的最短路径,如果没有正确的方法胡乱想确实很难算出来,并且如果暴力匹配复杂度呈指数级上升不适合解决实际问题。


那么我们该怎么想呢?


Dijkstra算法的前提


  1. 首先,Dijkstra处理的是带正权值的有权图,那么,就需要一个二维数组(如果空间大用list数组)存储各个点到达()的权值大小。(邻接矩阵或者邻接表存储)
  2. 其次,还需要一个boolean数组判断那些点已经确定最短长度,那些点没有确定。int数组记录距离(在算法执行过程可能被多次更新)。
  3. 需要优先队列加入已经确定点的周围点。每次抛出确定最短路径的那个并且确定最短,直到所有点路径确定最短为止。


简单的概括流程为


  • 一般从选定点开始抛入优先队列。(路径一般为0),boolean数组标记0的位置(最短为0) , 然后0周围连通的点抛入优先队列中(可能是node类),并把各个点的距离记录到对应数组内(如果小于就更新,大于就不动,初始第一次是无穷肯定会更新),第一次就结束了
  • 从队列中抛出距离最近的那个点B第一次就是0周围邻居)。这个点距离一定是最近的(所有权值都是正的,点的距离只能越来越长。)标记这个点为true并且将这个点的邻居加入队列(下一次确定的最短点在前面未确定和这个点邻居中产生),并更新通过B点计算各个位置的长度,如果小于则更新!


20190913132647145.png


重复二的操作,直到所有点都确定。


20190913133500806.png


算法实现



package 图论;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class dijkstra {
  static class node
  {
    int x; //节点编号
    int lenth;//长度
    public node(int x,int lenth) {
      this.x=x;
      this.lenth=lenth;
    }
  }
  public static void main(String[] args) {
    int[][] map = new int[6][6];//记录权值,顺便记录链接情况,可以考虑附加邻接表
    initmap(map);//初始化
    boolean bool[]=new boolean[6];//判断是否已经确定
    int len[]=new int[6];//长度
    for(int i=0;i<6;i++)
    {
      len[i]=Integer.MAX_VALUE;
    }
    Queue<node>q1=new PriorityQueue<node>(com);
    len[0]=0;//从0这个点开始
    q1.add(new node(0, 0));
    int count=0;//计算执行了几次dijkstra
    while (!q1.isEmpty()) {
      node t1=q1.poll();
      int index=t1.x;//节点编号
      int length=t1.lenth;//节点当前点距离
      bool[index]=true;//抛出的点确定
      count++;//其实执行了6次就可以确定就不需要继续执行了  这句可有可无,有了减少计算次数
      for(int i=0;i<map[index].length;i++)
      {
        if(map[index][i]>0&&!bool[i])
        {
          node node=new node(i, length+map[index][i]);
          if(len[i]>node.lenth)//需要更新节点的时候更新节点并加入队列
          {
            len[i]=node.lenth;
            q1.add(node);
          }
        }
      }
    }   
    for(int i=0;i<6;i++)
    {
      System.out.println(len[i]);
    }
  }
  static Comparator<node>com=new Comparator<node>() {
    public int compare(node o1, node o2) {
      return o1.lenth-o2.lenth;
    }
  };
  private static void initmap(int[][] map) {
    map[0][1]=2;map[0][2]=3;map[0][3]=6;
    map[1][0]=2;map[1][4]=4;map[1][5]=6;
    map[2][0]=3;map[2][3]=2;
    map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3;
    map[4][1]=4;map[4][3]=1;
    map[5][1]=6;map[5][3]=3;  
  }
}


执行结果:


20190915181948987.png


当然,dijkstra算法比较灵活,实现方式也可能有点区别,但是思想是不变的:一个贪心思路。dijkstra执行一次就能够确定一个点,所以只需要执行点的总和次数即可完成整个算法。

欢迎感谢小伙伴点赞、关注,赠人玫瑰,手有余香!蟹蟹!

目录
打赏
0
0
0
0
17
分享
相关文章
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
261 6
|
1月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
48 9
 算法系列之数据结构-二叉树
|
29天前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
42 3
 算法系列之数据结构-Huffman树
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
148 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
69 22
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
103 29
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
131 25
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
88 23
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
75 15
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
99 20

热门文章

最新文章

  • 1
    为什么要学习数据结构与算法
    26
  • 2
    局域网屏幕监控系统中的Python数据结构与算法实现
    142
  • 3
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    66
  • 4
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    55
  • 5
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    59
  • 6
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    82
  • 7
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    47
  • 8
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    84
  • 9
    2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    51
  • 10
    2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    59